d-Hitting Set问题的固定参数化算法
| 主要符号与默认约定 | 第1-10页 |
| 摘要 | 第10-12页 |
| ABSTRACT | 第12-15页 |
| 第一章 绪论 | 第15-25页 |
| §1.1 背景简介 | 第15-20页 |
| ·d-Hittinng Set问题 | 第15-17页 |
| ·参数复杂性 | 第17-20页 |
| §1.2 研究的动机 | 第20-21页 |
| §1.3 论文的贡献 | 第21-22页 |
| §1.4 论文的结构 | 第22-25页 |
| 第二章 预备知识 | 第25-47页 |
| §2.1 计算理论 | 第25-28页 |
| §2.2 图论知识 | 第28-32页 |
| §2.3 逻辑知识 | 第32-38页 |
| §2.4 参数复杂性 | 第38-47页 |
| ·电路刻画 | 第38-39页 |
| ·逻辑刻画 | 第39-40页 |
| ·机器刻画 | 第40-47页 |
| 第三章 核化算法 | 第47-75页 |
| §3.1 约减规则 | 第47-58页 |
| ·节点覆盖问题 | 第47-52页 |
| ·3-一致超图节点覆盖问题 | 第52-56页 |
| ·d-一致超图节点覆盖问题 | 第56-58页 |
| §3.2 皇冠约减 | 第58-64页 |
| ·节点覆盖问题 | 第58-61页 |
| ·3-一致超图节点覆盖问题 | 第61-63页 |
| ·d-一致超图节点覆盖问题 | 第63-64页 |
| §3.3 线性规划 | 第64-69页 |
| ·节点覆盖问题 | 第64-69页 |
| ·d-一致超图节点覆盖问题 | 第69页 |
| §3.4 网络流 | 第69-72页 |
| §3.5 小结 | 第72-75页 |
| 第四章 d-Hitting Set问题 | 第75-109页 |
| §4.1 度数受限的d-一致超图 | 第75-79页 |
| §4.2 平面的3-一致超图 | 第79-98页 |
| ·关联的问题 | 第79-81页 |
| ·平面图的支配集问题 | 第81-85页 |
| ·支配集问题的约减规则 | 第85-93页 |
| ·核大小 | 第93-97页 |
| ·核化算法 | 第97-98页 |
| §4.3 拟正则的d-一致超图 | 第98-107页 |
| §4.4 小结 | 第107-109页 |
| 第五章 对偶问题 | 第109-127页 |
| §5.1 独立集问题 | 第109-110页 |
| §5.2 度数受限的d-一致超图 | 第110-114页 |
| §5.3 平面的3-一致超图 | 第114-117页 |
| ·相关问题 | 第114-116页 |
| ·核化算法 | 第116-117页 |
| §5.4 拟正则的d-一致超图 | 第117-121页 |
| §5.5 核化算法的下界 | 第121-125页 |
| §5.6 小结 | 第125-127页 |
| 第六章 搜索树算法 | 第127-149页 |
| §6.1 节点覆盖问题 | 第128-140页 |
| ·动态规划 | 第128-129页 |
| ·树分解 | 第129-131页 |
| ·约减分支规则 | 第131-140页 |
| §6.2 3-Hitting Set问题 | 第140-145页 |
| ·启发式规则 | 第141页 |
| ·算法分析 | 第141-145页 |
| §6.3 拟凸规划分析 | 第145-147页 |
| §6.4 小结 | 第147-149页 |
| 第七章 总结与展望 | 第149-153页 |
| §7.1 总结 | 第149-150页 |
| §7.2 展望 | 第150-153页 |
| 索引 | 第153-159页 |
| 参考文献 | 第159-169页 |
| 附录A | 第169-179页 |
| 附录B | 第179-191页 |
| 致谢 | 第191-192页 |
| 攻读博士学位期间发表的学术论文 | 第192-193页 |
| 攻读博士学位期间参加的项目 | 第193-195页 |
