集合覆蓋問題是組合優(yōu)化領(lǐng)域中的經(jīng)典問題,它指的是在給定的集族中選一個階數(shù)最小子集族來覆蓋所有給定的元素.該問題不僅具有很高的理論價值,隨著無線網(wǎng)絡(luò)的發(fā)展更具有了越來越廣泛的應(yīng)用背景.本文主要研究的是集合覆蓋的兩種變形:最小賦權(quán)部分連通集合覆蓋問題（MVW PCSC）和在線3-路點(diǎn)覆蓋問題（online VCP3）.對于MWPCSC問題,給定元素集合U,集合族S,權(quán)函數(shù)c:S → Q+,以集合族中集合作為點(diǎn)集的連通圖GS,正整數(shù)k≤|U|,其目標(biāo)是找到一個最小權(quán)的子集族S’（?）S使得由S’導(dǎo)出的子圖連通,且|US∈S’S|≥k.當(dāng)GS滿足任意兩個有公共元素的集合在Gs中的跳數(shù)（hop distance）不超過r時,這個問題被稱為r-hopPCSC.對最小權(quán)的1-hopPCSC,我們給出了一個O(ln（m+ n）-近似算法;對最小基數(shù)下r-hopPCSC,我們給出了一個O（ln（m + n））-近似算法.和前人的結(jié)果比較,我們的方法要簡單的多.對于特殊集合覆蓋問題——3-路點(diǎn)覆蓋,給定圖G（V,E）,當(dāng)圖G中的每一條3個點(diǎn)的路至少有一個點(diǎn)在C中時,我們稱C是一個3-路點(diǎn)覆蓋.本文考慮的是... 

【文章來源】：浙江師范大學(xué)浙江省

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

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

【部分圖文】：

圖４．２：斷言２的圖示．用黑色的邊代替將會導(dǎo)出一個更大的３－路匹配．??

圖４．３：斷言３．?１．的證明圖示??

廁匪??⑷?（ｂ）??圖４．３：斷言３．?１．的證明圖示??斷言３．２．?Ｉｆ?Ｐ?ｅ?Ｍｉ，那么Ｘ?△?－?２，?Ｐ的硬幣能分擔(dān)到Ｐ＇上．??設(shè)尸＇＝．在ｃＰ，?＝?｜ｉ＼＾ｌｕＫ，（＼／（Ｐ）＼Ｃ）｜?＝?△?－?１的假設(shè)下，我們推出矛盾．??首先，考慮?＜?是ｎＣ？中的唯一點(diǎn)．如果ｕ?由于％己經(jīng)有三個鄰??點(diǎn)在Ｖ（Ｍ）中（如圖４．４⑷），那么丨￣婦，㈨）｜?＜?Ａ－３？結(jié)合｜ｉＶＫｌＵｉｒ，（｛ｚ４，４｝）｜?＝??｜」Ｖ／ｓ：ｌＵ／ｌ￡＂＇（＇ｌ’（／：＞）＼（７）｜?＝?Ａ?－?１，可知?（圮）｜?２?２．令為中兩點(diǎn)？那??么（＾／＾｛叩仰，１��；丨＋⑴是一個比ｉＵ更大的３－路匹酉己如果??■ｕ?＝?％


本文編號：2963165