Article ID Journal Published Year Pages File Type
6871866 Discrete Applied Mathematics 2016 20 Pages PDF
Abstract
We show that hitting set and set cover problems with half-strips oriented in two opposite directions are NP-complete. Further, we prove that two variations of the generalized class cover problem on half-strips oriented in two opposite directions are NP-complete, thus resolving two open problems we posed in Mudgal and Pandit (2014) [12].
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
Authors
, ,