一种基于混合策略的彩色编码算法  

An Improved Color Coding Algorithm Based on Hybrid Architecture

作　　者：王建新[1] 杨志彪[1] 刘云龙[1] 陈建二[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机学报》2010年第6期1024-1031,共8页Chinese Journal of Computers

基　　金：国家自然科学基金(60773111);国家"九七三"重点基础研究发展规划项目前期研究专项(2008CB317107);高等学校博士学科点专项科研基金项目(20090162110056);国家教育部创新团队资助计划(IRT0661)资助~~

摘　　要：彩色编码是求解实际工程中难解问题的一种新兴而重要的技术.在应用该技术时,算法复杂度取决于彩色编码着色方案的规模,因此规模的大小将成为衡量彩色编码算法优劣的标准.彩色编码的研究在最近几年得到了许多有重要意义的结果.基于完全散列函数的PH算法产生的着色方案规模为O*(6.1kn),是目前世界上最好的确定彩色编码结果;彩色编码算法PBCC是一种利用组合思想针对n 2k的有效着色算法.文中以分治算法为基础,结合核心化技术,并利用PBCC算法求解子问题,提出了一种基于混合策略的彩色编码算法HABCC,并且证明了由HABCC算法产生的着色方案确实可以覆盖到所有子集,着色方案规模为|S(n,k)|2k.logkk-1.n.通过与PH算法的比较,说明了HABCC算法具有更小的着色方案规模,对彩色编码技术的实际应用具有重要的意义.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≤2k.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· log k k^-1·n.Via comparing with PH algorithm,HABCC algorithm constructs a smaller coloring scheme,which is significant to practical application of color coding technology.

关 键 词：彩色编码 分治 核心化 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]