组合算法中的彩色编码技术研究

摘要

彩色编码(color-coding)是目前算法中重要的参数化技术之一。该技术已经在许多领域如k-PATH、子图同构、matching和packing等许多领域得到了应用。从这个意义上说，color-coding是算法领域中一个基础性问题：它的改进将带来算法在不同领域中一系列突破性进展。而在应用彩色编码时，所使用着色数目极大影响着问题求解性能，因此在应用该技术的时候算法应当尽可能地减少使用的着色数目。其中随机算法使用规模为O(e<'k>)的着色集合可以得到相对可靠的解；而确定算法则需要使用相对更大的着色方案。目前主流着色方案构造算法均基于完全散列函数和小参数理论，该技术近年发展迅速，其中J.Chen等人的算法可在O<'*>(6.1<'k>)时间内将彩色编码确定化。 在详细分析彩色编码技术的原理和应用的基础上，作者提出了一种基于划分的着色方案构造算法(PBCC)，解决了目前小参数算法在n≤2k的情况下效率低下的问题。作者也通过比较PBCC产生方案的规模渐近上界，在n≤2k下方案规模的渐近下界，以及穷举算法复杂度的下界，从理论上证明了PBCC算法的有效性。继而，在分治思想的框架上，基于PBCC算法和完全散列函数的思想，综合各种技术的优点，作者进一步提出了混合结构着色算法(HABCC)，将算法的应用范围由n≤2k扩展到任意的参数(n，k)组合。经实验检验，在实际条件下综合各算法优势的HABCC算法产生的方案规模远远小于原有小参数算法所产生的方案规模。此外，作者还推导了彩色编码问题中的一些理论界限，这些界限的证明对目前的算法分析和今后的算法设计都是有指导意义的。最后，作者对目前彩色编码的研究工作进行了总结，并讨论了在该领域中进一步研究的方向。

目录

文摘

英文文摘

声明

第一章引言

1.1组合问题简述

1.2 Color-coding的产生

1.3 Color-coding的应用

1.3.1κ-PATH及其相关问题的改进和应用

1.3.2子图同构问题

1.3.3 Matching和Packing

1.3.4 Ad-Hoc环加密技术及应用

1.3.5其他参数化问题

1.4彩色编码的研究内容

1.5论文的组织

第二章Color-coding技术

2.1着色方案的构造算法

2.1.1随机式color-coding

2.1.2确定式color-coding

2.2 Color-coding的形式化定义

2.3着色和组合

第三章PBCC算法

3.1 PBCC算法的基本思想

3.2简单情况下的着色方案

3.3一般情况下的PBCC算法

3.4 PBCC在(20，16)-motif查找中的应用

3.5 PBCC算法的正确性

3.6 PBCC算法的着色方案规模

3.7 PBCC算法的渐近上界

3.8着色方案规模下界分析

3.9着色方案规模的严格下界

3.10着色方案规模的渐近下界

第四章HABCC算法

4.1分治算法

4.2完全散列函数

4.3 PBCC算法

4.4混合着色算法

4.5 HABCC算法的正确性

4.6 PH算法实际生成方案规模分析

4.7 HABCC算法的性能

第五章结束语

5.1研究开发工作总结

5.2未来的工作

参考文献

致谢

攻读硕士期间的主要研究成果