| 两类广义控制问题的NP-完全性 |
| |
| 引用本文： | 赵伟良,赵衍才,梁作松.两类广义控制问题的NP-完全性[J].运筹学学报,2012,16(3):139-144. |
| |
| 作者姓名： | 赵伟良 赵衍才 梁作松 |
| |
| 作者单位： | 1. 浙江工业职业技术学院
2. 无锡城市职业技术学院
3. 蚌埠学院数学与物理系
4. 上海大学数学系 |
| |
| 基金项目： | supported by the foundation from Department of Education of Zhejiang Province (No.Y201018696);the Nature Science Foundation of Anhui Provincial Education Department(No. KJ2011B090) |
| |
| 摘 要： | 研究两类广义控制问题的复杂性: k-步长控制问题和k-距离控制问题, 证明了k-步长控制问题在弦图和平面二部图上都是NP-完全的. 作为上述结果的推论, 给出了k-距离控制问题在弦图和二部图上NP-完全性的新的证明, 并进一步证明了k-距离控制问题在平面二部图上也是NP-完全的.
|
| 关 键 词： | k-步长控制 k-距离控制 NP-完全性 弦图 平面二部图 |
| 收稿时间： | 2012-03-21 |
| 修稿时间： | 2012-05-16 |
NP-completeness for two generalized domination problems |
| |
| ZHAO Weiliang
,
ZHAO Yancai
,
LIANG Zuosong.NP-completeness for two generalized domination problems[J].OR Transactions,2012,16(3):139-144. |
| |
| Authors: | ZHAO Weiliang ZHAO Yancai LIANG Zuosong |
| |
| Institution: | 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 |
| |
| Abstract: | We study the complexity of two classes of generalized domination problems: A:-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. |
| |
| Keywords: | k-step domination k-distance domination NP-completeness chordal graphs planar bipartite graphs |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
