English

运筹学学报 ›› 2012, Vol. 16 ›› Issue (3): 139-144.

• 运筹学 • 上一篇    

两类广义控制问题的NP-完全性

赵伟良1, 赵衍才2,3, 梁作松4   

  1. 1. 浙江工业职业技术学院
    2. 无锡城市职业技术学院
    3. 蚌埠学院数学与物理系 4. 上海大学数学系
  • 收稿日期:2012-03-21 修回日期:2012-05-16 出版日期:2012-09-15 发布日期:2012-09-18
  • 通讯作者: 赵伟良 E-mail:zwl@shu.edu.cn

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

摘要： 研究两类广义控制问题的复杂性: k-步长控制问题和k-距离控制问题, 证明了k-步长控制问题在弦图和平面二部图上都是NP-完全的. 作为上述结果的推论, 给出了k-距离控制问题在弦图和二部图上NP-完全性的新的证明, 并进一步证明了k-距离控制问题在平面二部图上也是NP-完全的.

关键词: k-步长控制, k-距离控制, NP-完全性, 弦图, 平面二部图

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

中图分类号: