声明
第一章 绪 论
1.1 研究工作的背景及意义
1.2 国内外研究现状
1.2.1 最大k-plex问题
1.2.2 最大k-club问题
1.2.3 最大k-bundle问题
1.2.4 最小染色和问题
1.3 本文主要贡献与创新
1.4 论文结构安排
第二章 松弛团的定义和基本性质
2.1 符号和术语
2.2 朴素松弛团
2.3 二分团与二分松弛团
2.4 遗传性质
2.5 本章小结
第三章 最大k-plex问题的精确算法
3.1 问题定义及性质
3.2 分支规则
3.3 分支定界算法
3.4 实验结果
3.5 本章小结
第四章 最大k-bundle问题的精确算法
4.1 问题定义
4.2 遗传性及复杂度
4.3 规约规则
4.4 分支规则
4.5 分支定界算法
4.6 实验结果
4.6.1 随机图
4.6.2 第二届DIMACS图
4.6.3 SNAP和第十届DIMACS图
4.6.4 搜索树比较
4.7 本章小结
第五章 基于二分松弛团的最小染色和问题下界分析
5.1 问题定义及性质
5.2 已知理论下界回顾
5.2.1 Kokos(i)nski和Kwarciany提出的下界
5.2.2 Lecat等人提出的下界
5.3 新理论下界
5.3.1 新下界Ⅰ
5.3.2 新下界Ⅱ
5.4 实验结果
5.5 本章小结
第六章 总结与展望
6.1 全文总结
6.2 后续工作展望
致谢
参考文献
攻读硕士学位期间取得的成果