| 摘要 | 第4-6页 |
| Abstract | 第6-7页 |
| 1 引言 | 第10-29页 |
| 1.1 课题背景及研究意义 | 第10-16页 |
| 1.2 课题来源及研究目标 | 第16-18页 |
| 1.3 国内外研究现状 | 第18-25页 |
| 1.4 NP-hard问题算法评价 | 第25-27页 |
| 1.5 本文的结构 | 第27-29页 |
| 2 最大团问题及分支定界算法基础 | 第29-49页 |
| 2.1 定义与符号 | 第29-31页 |
| 2.2 最大团问题 | 第31-34页 |
| 2.3 分支定界方案 | 第34-37页 |
| 2.4 定界策略 | 第37-43页 |
| 2.5 分支策略 | 第43-48页 |
| 2.6 本章小节 | 第48-49页 |
| 3 渐进MaxSAT推理 | 第49-70页 |
| 3.1 MaxSAT问题 | 第49-51页 |
| 3.2 最大团问题的MaxSAT编码 | 第51-54页 |
| 3.3 标准MaxSAT推理——改进上界估计 | 第54-63页 |
| 3.4 渐进MaxSAT推理——减少分支数量 | 第63-67页 |
| 3.5 一个实际的图例 | 第67-69页 |
| 3.6 本章小节 | 第69-70页 |
| 4 结合渐进MaxSAT推理与动静态分支策略的高效算法 | 第70-102页 |
| 4.1 基本的算法框架MC1及算法DoMC1_(d0)、DoMC1和SoMC1 | 第70-78页 |
| 4.2 邻接矩阵重建和渐进上界 | 第78-85页 |
| 4.3 改进的算法框架MC2及算法DoMC2_(d0)、DoMC2和SoMC2 | 第85-89页 |
| 4.4 混合分支顺序算法MoMC | 第89-91页 |
| 4.5 实验结果与分析 | 第91-99页 |
| 4.6 本章小节 | 第99-102页 |
| 5 结合高效预处理与渐进MaxSAT推理的大稀疏图算法 | 第102-123页 |
| 5.1 大图中的最大团问题 | 第102-104页 |
| 5.2 基于core的最大团上界 | 第104-107页 |
| 5.3 大稀疏图算法LMC | 第107-113页 |
| 5.4 实验结果与分析 | 第113-122页 |
| 5.5 本章小节 | 第122-123页 |
| 6 冲突驱动的顶点权重切分与加权最大团算法 | 第123-156页 |
| 6.1 加权最大团问题 | 第123-128页 |
| 6.2 基于冲突独立集探测的上界 | 第128-130页 |
| 6.3 冲突驱动的顶点权重切分 | 第130-136页 |
| 6.4 加权最大团算法WLMC | 第136-145页 |
| 6.5 实验结果与分析 | 第145-155页 |
| 6.6 本章小节 | 第155-156页 |
| 7 总结与展望 | 第156-159页 |
| 致谢 | 第159-160页 |
| 参考文献 | 第160-173页 |
| 附录1 攻读学位期间发表论文及专利目录 | 第173-174页 |
| 附录2 攻读博士学位期间申请的发明专利和其他成果 | 第174-175页 |
| 附录3 攻读博士学位期间参与的科研项目 | 第175页 |
