无向路图和块图上的混合控制

作者：赵衍才; 单而芳; 王海超

来源：数学学报(中文版), 2017, 60(04): 641-650.

• 混合控制
• 无向路图
• 块图
• 算法
• NP-完全性

图G=（V,E）的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制问题在无向路图上是NP-完全的,但在块图上有线性时间算法.无向路图和块图都是弦图的子类,又是树的母类.

• 单位
  无锡城市职业技术学院; 上海电力学院; 上海大学