版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、支配集(Dominating Set)問題是一個經(jīng)典算法圖論問題,其在計算機無線網(wǎng)絡路由、生物計算、選舉、警衛(wèi)巡邏、地點選址等許多領域中都有著廣泛的應用。
人們在研究中發(fā)現(xiàn)支配集問題不僅是NP難問題,而且在參數(shù)復雜性理論中仍是W[2]完全問題,因此很難得到有效的算法結果。近年來特殊圖上的支配集問題引起了人們的重視,并取得了一些重要的成果。目前已經(jīng)證明其在Ki,j-free圖類上是固定參數(shù)可解的(Fixed-paramete
2、rized tractable,簡稱FPT)且具有多項式核。本文在平面支配集問題的研究基礎上,研究了若干特殊支配集在平面圖上的核心化結果。主要基于區(qū)域分解(region decomposition)技術對平面c連通m支配集問題、平面完全m支配集問題、平面m元支配集問題這三類問題的核心化做了深入的分析,得到了相應的線性核結果,首次表明這些問題是FPT可解的,并且表明了該結果是緊的。
本文還在上述結果的基礎上結合無線網(wǎng)絡路由問
3、題,提出了更為寬泛的一類支配集定義,即c點連通(mα,mβ)支配集問題,并證明該問題在mβ≥mα≥0的情況下在平面圖上仍是NP完全的。首先,從核心化的角度揭示了多連通性與多部支配性的等價性,從而減少了問題的參數(shù),然后提出了一條一般核心化規(guī)則,從而表明該問題在mβ≤2且mα×mβ×max(c,1)≠1的情況下有一個大小為(max(c,mα)+6)×(3|S|-6)的線性核,在mβ≥3情況下問題的規(guī)模至多為(mβ|S|-4)/(mβ-2),
最新文檔
- 平面圖和1-平面圖的若干染色問題.pdf
- 若干類圖支配問題的研究.pdf
- 關于生成樹和支配集問題的若干研究.pdf
- 平面點集的若干ERDOS問題.pdf
- 關于1-平面圖的若干列表染色的問題研究.pdf
- 平面圖染色問題的研究.pdf
- 若干平面圖的邊覆蓋染色.pdf
- 若干圖修改問題的參數(shù)算法及核心化研究.pdf
- 移動Ad Hoc網(wǎng)絡中連通支配集若干關鍵問題的研究.pdf
- 圖的支配問題研究.pdf
- 平面圖的強迫集、反強迫集與交錯集之間的關系.pdf
- 若干圖的等全著色及彩虹支配問題的研究.pdf
- 加權邊支配集問題的參數(shù)算法研究.pdf
- 圖的支配臨界問題研究.pdf
- 若干特殊平面圖的線性2-蔭度.pdf
- 平面圖
- 平面圖和定向平面圖的存活率.pdf
- 關于可平面圖的邊剖分的若干結果.pdf
- 若干圖的素標號和FFI集問題研究.pdf
- 1-平面圖正常點染色問題的研究.pdf
評論
0/150
提交評論