We study the geometric version of the minimum-membership dominating set problem. In this problem, we are given a set O of geometric objects in the plane, and the goal is to find a dominating set S of O such that the maximum number of dominators in S for each object in O is the minimum. We call the maximum number of dominators in S of any object is called the depth of S. We give a polynomial-time exact algorithm for the problem when the objects are intervals on the real line. Further, the problem has polynomial-time algorithms when the objects are axis-parallel lines and axis-parallel strips. On the other hand, the discrete version of the problem is \(\textsf{NP}\) -hard, even for depth 1, for axis-parallel lines, axis-parallel strips, and axis-parallel rectangles. Finally,  we show that the problem is \(\textsf{NP}\) -hard (for depth 1) when the objects are axis-parallel unit segments in the plane.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Minimum-Membership Geometric Dominating Set: Complexity and Algorithms

  • Bhavya Bansal,
  • Raghunath Reddy Madireddy,
  • Supantha Pandit

摘要

We study the geometric version of the minimum-membership dominating set problem. In this problem, we are given a set O of geometric objects in the plane, and the goal is to find a dominating set S of O such that the maximum number of dominators in S for each object in O is the minimum. We call the maximum number of dominators in S of any object is called the depth of S. We give a polynomial-time exact algorithm for the problem when the objects are intervals on the real line. Further, the problem has polynomial-time algorithms when the objects are axis-parallel lines and axis-parallel strips. On the other hand, the discrete version of the problem is \(\textsf{NP}\) -hard, even for depth 1, for axis-parallel lines, axis-parallel strips, and axis-parallel rectangles. Finally,  we show that the problem is \(\textsf{NP}\) -hard (for depth 1) when the objects are axis-parallel unit segments in the plane.