若干平面圖支配集問題的核心化研究.pdf

1、支配集(Dominating Set)問題是一個經典算法圖論問題,其在計算機無線網絡路由、生物計算、選舉、警衛(wèi)巡邏、地點選址等許多領域中都有著廣泛的應用。
　　 人們在研究中發(fā)現支配集問題不僅是NP難問題,而且在參數復雜性理論中仍是W[2]完全問題,因此很難得到有效的算法結果。近年來特殊圖上的支配集問題引起了人們的重視,并取得了一些重要的成果。目前已經證明其在Ki,j-free圖類上是固定參數可解的(Fixed-paramete

2、rized tractable,簡稱FPT)且具有多項式核。本文在平面支配集問題的研究基礎上,研究了若干特殊支配集在平面圖上的核心化結果。主要基于區(qū)域分解(region decomposition)技術對平面c連通m支配集問題、平面完全m支配集問題、平面m元支配集問題這三類問題的核心化做了深入的分析,得到了相應的線性核結果,首次表明這些問題是FPT可解的,并且表明了該結果是緊的。
　　 本文還在上述結果的基礎上結合無線網絡路由問

3、題,提出了更為寬泛的一類支配集定義,即c點連通(mα,mβ)支配集問題,并證明該問題在mβ≥mα≥0的情況下在平面圖上仍是NP完全的。首先,從核心化的角度揭示了多連通性與多部支配性的等價性,從而減少了問題的參數,然后提出了一條一般核心化規(guī)則,從而表明該問題在mβ≤2且mα×mβ×max(c,1)≠1的情況下有一個大小為(max(c,mα)+6)×(3|S|-6)的線性核,在mβ≥3情況下問題的規(guī)模至多為(mβ|S|-4)/(mβ-2),