| 无向路图和块图上的混合控制 |
| |
| 引用本文： | 赵衍才,单而芳,王海超.无向路图和块图上的混合控制[J].数学学报,2017,60(4):641-650. |
| |
| 作者姓名： | 赵衍才 单而芳 王海超 |
| |
| 作者单位： | 1. 无锡城市职业技术学院 无锡 214153;
2. 上海大学管理学院 上海 200444;
3. 上海电力学院 上海 200090 |
| |
| 基金项目： | 国家自然科学基金资助项目（11571222）；江苏省自然科学基金（基础研究计划： BK20151117）；上海市自然科学基金（14ZR1417900） |
| |
| 摘 要： | 图G=(V,E)的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制问题在无向路图上是NP-完全的,但在块图上有线性时间算法.无向路图和块图都是弦图的子类,又是树的母类.
|
| 关 键 词： | 混合控制 无向路图 块图 算法 NP-完全性 |
Mixed Domination in Undirected Path Graphs and Block Graphs |
| |
| Yan Cai ZHAO,Er Fang SHAN,Hai Chao WANG.Mixed Domination in Undirected Path Graphs and Block Graphs[J].Acta Mathematica Sinica,2017,60(4):641-650. |
| |
| Authors: | Yan Cai ZHAO Er Fang SHAN Hai Chao WANG |
| |
| Institution: | 1. Wuxi City College of Vocational Technology, Wuxi 214153, P. R. China;
2. School of Management, Shanghai University, Shanghai 200444, P. R. China;
3. Shanghai University of Electric Power, Shanghai 200090, P. R. China |
| |
| Abstract: | A mixed dominating set of a graph G=(V,E) is a set D ⊆ V ∪ E such that every vertex or edge not in D is adjacent or incident to at least one vertex or edge in D.The mixed domination problem is to determine a minimum mixed dominating set of G.This paper studies the complexity of mixed domination in graphs.We prove that the mixed domination problem remains NP-complete for undirected path graphs,and is solvable for block graphs.Both undirected path graphs and block graphs are subclasses of chordal graphs and superclasses of trees. |
| |
| Keywords: | mixed domination undirected path graph block graph algorithm Npcompleteness |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《数学学报》浏览原始摘要信息 |
| 点击此处可从《数学学报》下载免费的PDF全文 |
