两类广义控制问题的NP-完全性(英文)  

NP-completeness for two generalized domination problems

作　　者：赵伟良[1] 赵衍才[2,3] 梁作松[4] 

机构地区：[1]浙江工业职业技术学院,浙江绍兴312000 [2]无锡城市职业技术学院,江苏无锡214153 [3]蚌埠学院数学与物理系,安徽蚌埠233030 [4]上海大学数学系,上海200444

出　　处：《运筹学学报》2012年第3期139-144,共6页Operations Research Transactions

基　　金：supported by the foundation from Department of Education of Zhejiang Province (No.Y201018696);the Nature Science Foundation of Anhui Provincial Education Department(No. KJ2011B090)

摘　　要：研究两类广义控制问题的复杂性:κ-步长控制问题和κ-距离控制问题,证明了κ-步长控制问题在弦图和平面二部图上都是NP-完全的,作为上述结果的推论,给出了κ-距离控制问题在弦图和二部图上NP-完全性的新的证明,并进一步证明了κ-距离控制问题在平面二部图上也是NP-完全的。We study the complexity of two classes of generalized domination prob- lems： 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.

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

分 类 号：O223[理学—运筹学与控制论]