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

发布时间：2020-03-22 02:49

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

【相似文献】

相关期刊论文 前6条

1 杨振宇,陈宗基;递阶混合控制系统的分析、综合与证明[J];控制与决策;1998年01期

2 肖笛,程勉,高为炳;机器人的自适应混合控制[J];北京航空航天大学学报;1992年04期

3 杨振宇,陈宗基;基于HIOA~+模型的混合控制设计[J];信息与控制;1998年03期

4 张晓芹;康丽英;;块图中的无权1-中心问题[J];上海大学学报(自然科学版);2011年03期

5 程郁琨;;块图上的p-maxian问题[J];芜湖职业技术学院学报;2009年01期

6 李永欣;刘岩;;圈块图的最小Hosoya指数[J];华南师范大学学报(自然科学版);2011年04期

相关硕士学位论文 前1条

1 宁宇;块图的2-彩虹控制问题算法研究[D];华东师范大学;2011年

，

本文编号：2594351