参数算法中核心化和彩色编码技术的研究

摘要

核心化和彩色编码是两种重要的参数算法设计技术。核心化技术广泛应用于Cover、Packing和Cut等问题的研究，而彩色编码已成功应用于求解Path、Packing、Matching和GraphMotif等问题。因此，核心化和彩色编码技术的研究对于相关问题的求解具有重要的指导意义。 本文首先研究了参数化P2-Packing问题的核心化算法。现有的最好结果是J.Wang等人利用皇冠分解和局部简化技术得到的该问题7k大小核的算法。在此基础上，本文进一步分析了P2-Packing问题的结构，引入两条局部简化规则，提出了一种复杂度为O（k3（n+m））的核心化算法P2PK。经过分析，该算法可以得到P2-Packing问题的一个至多6k个点的核。在此基础上，本文提出了一种求解P2-Packing问题的参数算法，时间复杂度为O*（2.3713k），改进了目前文献中的最好结果。 此外，本文研究了彩色编码着色方案的构造算法。现有的最好结果是J.Chen等人提出的复杂度为O*（6.1k）的PH算法。PH算法基于完全散列函数，需要n远大于k且k较小的前提条件。另一方面，J.Wang等人利用组合思想，提出了n≤2k情况下的实用彩色编码算法PBCC。在此基础上，本文提出了一种基于混合策略的彩色编码算法HABCC，解决了彩色编码的适用性问题。本文进一步分析了HABCC算法的复杂度，证明了该算法产生的着色方案规模的上界为2k·「㏒k（）k-1·n。通过与PH算法比较，说明了HABCC算法能产生更小的着色方案，因而具有更好的实用性。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景

1.2研究现状

1.3研究内容

1.3.1 P2-Packing问题的核心化算法

1.3.2彩色编码着色方案构造算法

1.4研究意义

1.5论文的组织

第二章核心化和彩色编码算法

2.1核心化算法

2.1.1皇冠分解技术

2.1.2局部简化技术

2.1.3极值归纳技术

2.2彩色编码算法

2.2.1随机彩色编码

2.2.2确定彩色编码

2.3本章小结

第三章P2-Packing问题的核心化

3.1相关定义

3.2皇冠分解

3.3局部简化

3.4局部贪婪

3.5核心化算法P2PK

3.6参数算法P2PA

3.7算法分析

3.7.1算法正确性

3.7.2算法复杂度

3.8本章小结

第四章HABCC算法

4.1基本思想

4.2核心化预处理

4.3求解子问题

4.4 HABCC算法

4.5算法分析

4.5.1算法正确性

4.5.2算法复杂度

4.6本章小结

第五章结束语

5.1研究工作总结

5.2工作展望

参考文献

致谢

研究成果