無向圖中連通支配集問題的精確算法

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