無(wú)向圖中連通支配集問(wèn)題的精確算法

周曉清; 葉安勝; 張志強(qiáng) 電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院; 成都611731; 成都大學(xué)信息科學(xué)與工程學(xué)院; 成都610106

np難問(wèn)題
精確算法
測(cè)量治之
連通支配集問(wèn)題

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

注：因版權(quán)方要求，不能公開(kāi)全文，如需全文，請(qǐng)咨詢雜志社

投稿咨詢文秘咨詢