| 摘要 | 第1-6页 |
| ABSTRACT | 第6-10页 |
| 第一章 绪论 | 第10-19页 |
| ·研究背景 | 第10-12页 |
| ·研究现状 | 第12-16页 |
| ·参数计算与复杂性理论基础 | 第12-14页 |
| ·参数算法设计技术分类介绍 | 第14-16页 |
| ·研究内容 | 第16-17页 |
| ·参数化边-多端割扩展问题的局部核心化研究 | 第16-17页 |
| ·参数化边-多割问题的固定参数可解算法的研究 | 第17页 |
| ·研究意义 | 第17-18页 |
| ·论文结构 | 第18-19页 |
| 第二章 参数化边-多端割扩展问题的局部核心化 | 第19-55页 |
| ·引言 | 第19-24页 |
| ·相关术语和引理 | 第24-29页 |
| ·相关术语的定义 | 第24-26页 |
| ·相关引理的证明 | 第26-29页 |
| ·小超额边的局部核心化的有用性 | 第29-32页 |
| ·"诡计"图及其性质引理 | 第29-30页 |
| ·边超额至多为1的边-多端割问题的NP完全性 | 第30-32页 |
| ·问题结构的两个简单观察 | 第32-33页 |
| ·超额至多为1的边的局部核心化 | 第33-53页 |
| ·简化规则一及相关分析 | 第34-39页 |
| ·简化规则二及相关分析 | 第39-48页 |
| ·局部核心化的时间复杂度分析 | 第48-53页 |
| ·本章小结 | 第53-55页 |
| 第三章 参数化边-多割问题的固定参数可解算法 | 第55-72页 |
| ·引言 | 第55-57页 |
| ·参数化边-多端割扩展问题的固定参数可解算法 | 第57-64页 |
| ·终端集的最远最小切割 | 第57-60页 |
| ·参数化边-多端割扩展问题的算法及其证明 | 第60-64页 |
| ·参数化边-多割问题的固定参数可解算法 | 第64-71页 |
| ·参数化边-多割问题与参数化边-多端割扩展问题之间的联系 | 第64-66页 |
| ·集合{s_1,t_1,s_2,t_2,…,s_1,t_1}的极大恰当划分 | 第66-69页 |
| ·参数化边-多割问题的算法及其证明 | 第69-71页 |
| ·本章小结 | 第71-72页 |
| 第四章 总结与展望 | 第72-75页 |
| ·研究工作总结 | 第72-73页 |
| ·进一步研究展望 | 第73-75页 |
| 参考文献 | 第75-83页 |
| 致谢 | 第83-84页 |
| 攻读硕士学位期间主要的研究成果 | 第84页 |