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\) .

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

Partial Domination in Some Geometric Intersection Graphs

  • Madhura Dutta,
  • Anil Maheshwari,
  • Subhas C. Nandy

摘要

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\) .