An Improved Color Coding Algorithm Based on Hybrid Architecture
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
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 n2k. 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)|2k logk k-1n. Via comparing with PH algorithm, HABCC algorithm constructs a smaller coloring scheme, which is significant to practical application of color coding technology.
