【摘要】：圖G=(V,E)的一個混合控制集是一個滿足如下條件的集合D銰V∪E:不在D中的每個點或每條邊都相鄰或關(guān)聯(lián)于D中的至少一個點或一條邊.確定圖的最小基數(shù)的混合控制集的問題稱為混合控制問題.本文研究混合控制問題的算法復(fù)雜性,證明了混合控制問題在無向路圖上是NP-完全的,但在塊圖上有線性時間算法.無向路圖和塊圖都是弦圖的子類,又是樹的母類.

【相似文獻】

相關(guān)期刊論文 前6條

1 楊振宇,陳宗基;遞階混合控制系統(tǒng)的分析、綜合與證明[J];控制與決策;1998年01期

2 肖笛,程勉,高為炳;機器人的自適應(yīng)混合控制[J];北京航空航天大學(xué)學(xué)報;1992年04期

3 楊振宇,陳宗基;基于HIOA~+模型的混合控制設(shè)計[J];信息與控制;1998年03期

4 張曉芹;康麗英;;塊圖中的無權(quán)1-中心問題[J];上海大學(xué)學(xué)報(自然科學(xué)版);2011年03期

5 程郁琨;;塊圖上的p-maxian問題[J];蕪湖職業(yè)技術(shù)學(xué)院學(xué)報;2009年01期

6 李永欣;劉巖;;圈塊圖的最小Hosoya指數(shù)[J];華南師范大學(xué)學(xué)報(自然科學(xué)版);2011年04期

相關(guān)碩士學(xué)位論文 前1條

1 寧宇;塊圖的2-彩虹控制問題算法研究[D];華東師范大學(xué);2011年

，

本文編號：2594351