| 第一章 绪论 | 第1-9页 |
| 1．1 引言 | 第6页 |
| 1．2 课题研究内容 | 第6页 |
| 1．3 课题的研究现状 | 第6-7页 |
| 1．3．1 国外顶点覆盖问题的研究现状 | 第6-7页 |
| 1．3．2 国内顶点覆盖问题的研究现状 | 第7页 |
| 1．4 本文的研究目标 | 第7-9页 |
| 第二章 NP完全性理论 | 第9-20页 |
| 2．1 计算模型 | 第9-14页 |
| 2．1．1 图灵机 | 第10-12页 |
| 2．1．2 问题变换与计算复杂性归约 | 第12-14页 |
| 2．2 P类与NP类问题 | 第14-16页 |
| 2．2．1 非确定性图灵机 | 第14-15页 |
| 2．2．2 P类与NP类语言 | 第15-16页 |
| 2．3 NP完全问题 | 第16-20页 |
| 2．3．1 多项式时间变换 | 第16-18页 |
| 2．3．2 一些典型的NP完全问题 | 第18-20页 |
| 第三章 二分图顶点覆盖在芯片修复中的运用 | 第20-27页 |
| 3．1 图的基本概念 | 第20-21页 |
| 3．2 二分图顶点覆盖在芯片修复中的运用 | 第21-27页 |
| 3．2．1 二分图上受约束的顶点覆盖 | 第22-23页 |
| 3．2．2 MIN-FCRA是NP-完全问题 | 第23-27页 |
| 第四章 固定参数算法 | 第27-35页 |
| 4．1 固定参数算法理论 | 第27-29页 |
| 4．1．1 参数问题 | 第27页 |
| 4．1．2 思想 | 第27-28页 |
| 4．1．3 固定参数易解类型Fixed Parameter Tractability | 第28-29页 |
| 4．2 固定参数算法的技巧 | 第29-35页 |
| 4．2．1 介绍 | 第29页 |
| 4．2．2 化简问题核心 | 第29-31页 |
| 4．2．3 限定搜索树 | 第31-35页 |
| 第五章 FPT算法与CBVC问题的结合 | 第35-47页 |
| 5．1 匹配理论的相关问题 | 第35-36页 |
| 5．1．1 匹配理论的相关概念 | 第35页 |
| 5．1．2 Gallai-Edmonds结构定理 | 第35-36页 |
| 5．2 化简问题核心 | 第36-38页 |
| 5．3 限定搜索树(用Dulmage-Mendelsohn分解定理分解) | 第38-45页 |
| 5．3．1 Dulmage-Mendelsohn分解定理 | 第39-40页 |
| 5．3．2 限定搜索树 | 第40-45页 |
| 5．4 前面的综合 | 第45-47页 |
| 第六章 结论 | 第47-48页 |
| 参考文献 | 第48-51页 |
| 致谢 | 第51页 |
