中文

Operations Research Transactions ›› 2012, Vol. 16 ›› Issue (3): 139-144.

• Original Articles • Previous Articles    

NP-completeness for two generalized domination problems

ZHAO Weiliang1,  ZHAO Yancai2,3,  LIANG Zuosong4   

  1. 1. Zhejiang Industry Polytechnic College 2. Wuxi City College of Vocational Technology 3. Foundation of Mathematiics and Physics, Bengbu College 4. Department of Mathematics, Shanghai University
  • Received:2012-03-21 Revised:2012-05-16 Online:2012-09-15 Published:2012-09-18
  • Contact: ZHAO Weiliang E-mail:zwl@shu.edu.cn
  • Supported by:

    the foundation from Department of Education of Zhejiang Province (No.Y201018696), Nature Science Foundation of Anhui Provincial Education Department (No. KJ2011B090)

PDF

1362

Abstract: We study the complexity of two classes of generalized domination problems: k-step domination problem and k-distance domination problem. We prove that the decision version of k-step domination problem is NP-complete when instances are restricted to chordal graphs or planar bipartite graphs. As corollaries to the results, we obtain new proofs of the NP-completeness of k-distance domination problem for chordal graphs and bipartite graphs, and also prove that this problem remains NP-complete even when restricted to planar bipartite graphs.

Key words: k-step domination, k-distance domination, NP-completeness, chordal graphs, planar bipartite graphs

CLC Number: