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

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

【學位級別】：碩士

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



本文編號：4018008