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