Effective coloring algorithm for close relationship between the scales of element set and color set and its application
Academic Article
Overview
Additional Document Info
View All
Overview
abstract
Color-coding is one of the most important solutions to those problems proved to be NP-Hard. The performance of those color-coding based algorithms principally depends on the scale of the coloring schemes generated by coloring algorithms they deploy. Therefore, the ultimate objective of coloring algorithm is to provide a coloring scheme as small as possible. All existing coloring algorithms are mainly based on perfect hash functions, requiring of the number of elements n far greater than the number of colors k, and k relatively small. This paper mainly focuses on the study of effective algorithms under the circumstance where the size of element set and color set are close (n2k) and the analysis of performance of coloring algorithm while n 2k. This paper proposes a novel partition based algorithm PBCC, and proves that the coloring scheme generated by PBCC can cover all the subsets. A detailed method for constructing a (20, 16)-coloring scheme with size 403 which can be applied for (l, d)-(20, 16) motif finding problem is also provided. At last, using asymptotic analysis, it is proved that coloring scheme generated by PBCC is of size O(e2Rootof(x-(x)+1)(n-k)), and it is O(2.62n-k) when n = 2k. Also, it is showen that any coloring scheme with n 2k will be larger than 2n-k.
