An improved color coding algorithm based on hybrid architecture

作者：Wang Jian Xin^*; Yang Zhi Biao; Liu Yun Long; Chen Jian Er

来源：Chinese Journal of Computers, 2010, 33(6): 1024-1031.

DOI：10.3724/SP.J.1016.2010.01024

• Color coding
• Coloring algorithms
• Coloring schemes
• Complexity of algorithm
• Divide and conquer
• Divide-and-conquer algorithm
• Hard problems
• Hybrid architectures
• Kernelization
• Perfect hashing
• Scale sizes

Color coding is a new and important technique to solve engineering hard problems. The complexity of algorithm using color coding depends on the scale of the coloring schemes, so the scale size becomes a standard to measure the color coding algorithm. Recently, the researches of color coding received many important improvements. The PH (Perfect Hashing) algorithm based on perfect hash functions constructs a scheme of size O*(6.1kn), which has been the best deterministic result for color coding so far. The PBCC (Partition-Based Color-Coding) algorithm is an effective color coding algorithm using combination thought while n&le2k. Basing on divide-and-conquer algorithm, combining with kernelization technique and using PBCC algorithm to solve sub-problem, this paper proposes a hybrid architecture based coloring algorithm HABCC (Hybrid Architecture Based Color-Coding), and proves that the coloring scheme generated by HABCC can cover all the subsets, moreover, the scheme scale satisfying |S(n,k)|&le2k&middot⌈ logk ⌉k-1&middotn. Via comparing with PH algorithm, HABCC algorithm constructs a smaller coloring scheme, which is significant to practical application of color coding technology.

• 出版日期2010
• 单位中南大学