摘要：圖G=(V,E)的一個支配集D?V是一個頂點子集,使得圖中每一個頂點要么在D中,要么至少與D中的一個頂點相連。連通支配集問題是找到一個頂點數(shù)最小的支配集S,并且S的導(dǎo)出子圖G[S]是連通圖。該問題是一個經(jīng)典的NP難問題,可應(yīng)用于連通設(shè)施選址、自適應(yīng)網(wǎng)絡(luò)等領(lǐng)域。針對無向圖中連通支配集問題,仔細(xì)分析該問題的圖結(jié)構(gòu)性質(zhì),挖掘出若干有效的約簡規(guī)則和分支規(guī)則,設(shè)計了一個分支搜索算法,并采用了測量治之方法分析算法的運行時間,最終得到了一個運行時間復(fù)雜度為O*(1. 93n)的精確算法。