連通控制集問(wèn)題在計(jì)算機(jī)科學(xué),運(yùn)籌學(xué)等多個(gè)領(lǐng)域有廣泛的應(yīng)用.為了節(jié)約資源,圖的連通控制集常作為無(wú)線傳感器網(wǎng)絡(luò)的虛擬骨干.而由于無(wú)線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)容易發(fā)生故障,需要建立一個(gè)容錯(cuò)的虛擬骨干來(lái)保持一定程度的冗余,因此研究k-連通m-折疊控制集問(wèn)題是非常必要的.給定一個(gè)圖G,正整數(shù)k和m.設(shè)C是頂點(diǎn)集V的一個(gè)頂點(diǎn)子集,如果由C誘導(dǎo)的子圖k-連通,并且V\C中的每個(gè)頂點(diǎn)都與C中至少m個(gè)頂點(diǎn)相鄰,則稱C是圖G的一個(gè)k-連通m-折疊控制集.本文研究2-連通圖G上的最小2-連通m-折疊控制集問(wèn)題,給出一個(gè)貪婪算法,并證明該算法的近似比是ln(Δ+m+2)+5,其中△是圖G中頂點(diǎn)的最大度.

【文章頁(yè)數(shù)】：33 頁(yè)

【學(xué)位級(jí)別】：碩士

【文章目錄】：
中文摘要
英文摘要
引言
第一章 預(yù)備知識(shí)
    1.1 圖的基本概念
    1.2 圖的連通控制集
第二章 (2,m)-連通控制集的貪婪算法
    2.1 勢(shì)函數(shù)的構(gòu)作
    2.2 勢(shì)函數(shù)的性質(zhì)
    2.3 貪婪算法
第三章 算法的理論分析
    3.1 相關(guān)引理
    3.2 近似比分析
結(jié)論
參考文獻(xiàn)
致謝



本文編號(hào)：4018008