基于树分解的难解问题的参数算法研究
| 摘要 | 第4-6页 |
| Abstract | 第6-8页 |
| 目录 | 第9-11页 |
| 1 绪论 | 第11-23页 |
| 1.1 研究背景 | 第11-13页 |
| 1.2 参数计算理论基础 | 第13-15页 |
| 1.3 研究内容 | 第15-16页 |
| 1.4 研究意义 | 第16-17页 |
| 1.5 术语及关键技术 | 第17-21页 |
| 1.6 全文结构 | 第21-23页 |
| 2 参数计算在社会学和生物信息学中应用的介绍 | 第23-33页 |
| 2.1 参数计算在社会学中的应用 | 第23-28页 |
| 2.1.1 支配问题 | 第23-25页 |
| 2.1.2 投票问题 | 第25-27页 |
| 2.1.3 影响最大化问题 | 第27-28页 |
| 2.2 参数计算在生物信息学中的应用 | 第28-32页 |
| 2.2.1 序列比对 | 第29-30页 |
| 2.2.2 进化和发育 | 第30-31页 |
| 2.2.3 基因重排 | 第31-32页 |
| 2.3 本章小结 | 第32-33页 |
| 3 正负支配问题的参数算法 | 第33-51页 |
| 3.1 引言 | 第33-34页 |
| 3.2 复杂性证明 | 第34-36页 |
| 3.3 正负支配集问题的核心化 | 第36-45页 |
| 3.4 正负支配集问题的参数算法 | 第45-50页 |
| 3.4.1 正负支配集参数算法 | 第45页 |
| 3.4.2 平面正负支配集参数算法 | 第45-50页 |
| 3.5 本章小结 | 第50-51页 |
| 4 三值支配问题的参数算法 | 第51-71页 |
| 4.1 引言 | 第51-52页 |
| 4.2 复杂性证明 | 第52-63页 |
| 4.2.1 权值为参数 | 第52-57页 |
| 4.2.2 集合大小为参数 | 第57-63页 |
| 4.3 间隔图上的线性算法 | 第63-70页 |
| 4.4 本章小结 | 第70-71页 |
| 5 联盟问题的参数算法 | 第71-81页 |
| 5.1 引言 | 第71-73页 |
| 5.2 防守联盟和进攻联盟 | 第73-76页 |
| 5.2.1 参数算法 | 第73-75页 |
| 5.2.2 核下界 | 第75-76页 |
| 5.3 全局防守联盟和全局进攻联盟 | 第76-80页 |
| 5.3.1 限定树宽图上参数算法 | 第76-79页 |
| 5.3.2 核心化 | 第79-80页 |
| 5.4 本章小结 | 第80-81页 |
| 6 序列结构比对问题的参数算法 | 第81-94页 |
| 6.1 引言 | 第81-85页 |
| 6.2 复杂性证明 | 第85-87页 |
| 6.3 固定参数可解证明 | 第87-91页 |
| 6.4 序列结构比对问题的参数算法 | 第91-93页 |
| 6.5 本章小结 | 第93-94页 |
| 7 总结 | 第94-98页 |
| 7.1 主要贡献和创新点 | 第94-96页 |
| 7.2 展望 | 第96-98页 |
| 参考文献 | 第98-109页 |
| 攻读博士学位期间主要的研究成果 | 第109-110页 |
| 致谢 | 第110页 |
