Partial Domination in Some Geometric Intersection Graphs
摘要
Partial domination problem is a generalization of the minimum dominating set problem on graphs. Here, instead of dominating all the nodes, one asks to dominate at least a fraction of the nodes of the given graph by choosing a subset of nodes of minimum size. For any real number \(\alpha \in (0,1]\) , \(\alpha \) -partial domination problem can be proved to be NP-complete for general graphs. In this paper, we define the maximum dominating k-set of a graph which is polynomially transformable to the partial domination problem. We propose polynomial time algorithms for the maximum dominating k-set problem for some geometric intersection graphs, namely, interval graphs and unit square intersection graphs where the given squares are intersected by the straight line \(L: y=-x\) .