若干平面图支配集问题的核心化研究

摘要

支配集(Dominating Set)问题是一个经典算法图论问题,其在计算机无线网络路由、生物计算、选举、警卫巡逻、地点选址等许多领域中都有着广泛的应用。
　　 人们在研究中发现支配集问题不仅是NP难问题,而且在参数复杂性理论中仍是W[2]完全问题,因此很难得到有效的算法结果。近年来特殊图上的支配集问题引起了人们的重视,并取得了一些重要的成果。目前已经证明其在Ki,j-free图类上是固定参数可解的(Fixed-parameterized tractable,简称FPT)且具有多项式核。本文在平面支配集问题的研究基础上,研究了若干特殊支配集在平面图上的核心化结果。主要基于区域分解(region decomposition)技术对平面c连通m支配集问题、平面完全m支配集问题、平面m元支配集问题这三类问题的核心化做了深入的分析,得到了相应的线性核结果,首次表明这些问题是FPT可解的,并且表明了该结果是紧的。
　　 本文还在上述结果的基础上结合无线网络路由问题,提出了更为宽泛的一类支配集定义,即c点连通(mα,mβ)支配集问题,并证明该问题在mβ≥mα≥0的情况下在平面图上仍是NP完全的。首先,从核心化的角度揭示了多连通性与多部支配性的等价性,从而减少了问题的参数,然后提出了一条一般核心化规则,从而表明该问题在mβ≤2且mα×mβ×max(c,1)≠1的情况下有一个大小为(max(c,mα)+6)×(3|S|-6)的线性核,在mβ≥3情况下问题的规模至多为(mβ|S|-4)/(mβ-2),其中|S|为支配集的大小,首次表明该问题是FPT可解的。

目录

文摘

英文文摘

第一章 绪论

1.1 研究背景

1.2 研究内容

1.3 研究意义

1.4 论文组织

第二章 核心化及支配集问题的研究现状

2.1 基本定义

2.2 核心化

2.2.1 核心化的参数理论背景

2.2.2 核上界

2.2.3 核下界

2.3 支配集问题

2.3.1 支配集问题及其若干变形

2.3.2 参数化支配集问题的研究

2.4 小结

第三章 若干特殊支配集问题在平面图上的核心化

3.1 相关定义和引理

3.2 若干特殊支配集在平面图上的线性核

3.2.1 平面2/2元/完全2支配集问题

3.2.2 平面c连通m/m元/完全m支配集问题

3.3 小结

第四章 平面c连通(mα,mβ)支配集问题的核心化

4.1 平面(mα,mβ)支配集问题(mβ≥mα≥0)的NP完全性证明

4.2 平面c连通(mα,mβ)支配集问题的核心化算法

4.2.1 多连通性与多部支配

4.2.2 平面c连通(mα,mβ)支配集问题的线性核

4.3 小结

第五章 结束语

5.1 研究工作总结

5.2 后续研究工作展望

参考文献

致谢

研究成果