无向路图和块图上的混合控制
Mixed Domination in Undirected Path Graphs and Block Graphs作者机构：无锡城市职业技术学院无锡214153 上海大学管理学院上海200444 上海电力学院上海200090
出 版 物：《数学学报（中文版）》 (Acta Mathematica Sinica：Chinese Series)
年 卷 期：2017年第60卷第4期
页 面：641-650页
核心收录：
学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学]
基 金：国家自然科学基金资助项目(11571222) 江苏省自然科学基金(基础研究计划:BK20151117) 上海市自然科学基金(14ZR1417900)
摘 要：图G=(V,E)的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制问题在无向路图上是NP-完全的,但在块图上有线性时间算法.无向路图和块图都是弦图的子类,又是树的母类.
维普期刊数据库
同方期刊数据库