《计算机学报》文章摘要   全文下载
文章题目	一种基于混合策略的彩色编码算法
作者	王建新 杨志彪 刘云龙 陈建二
作者单位	(中南大学信息科学与工程学院 长沙410083)
发表年份	2010
发表月份	6期(1024—1031)
文章摘要	摘要 彩色编码是求解实际工程中难解问题的一种新兴而重要的技术.在应用该技术时，算法复杂度取决于彩色编码着色方案的规模，因此规模的大小将成为衡量彩色编码算法优劣的标准.彩色编码的研究在最近几年得到了许多有重要意义的结果.基于完全散列函数的PH算法产生的着色方案规模为O*(6.1kn)，是目前世界上最好的确定彩色编码结果；彩色编码算法PBCC是一种利用组合思想针对n≤2k的有效着色算法.文中以分治算法为基础，结合核心化技术，并利用PBCC算法求解子问题，提出了一种基于混合策略的彩色编码算法HABCC，并且证明了由HABCC算法产生的着色方案确实可以覆盖到所有子集，着色方案规模为｜S(n,k)｜≤2k?[logk]k-1?n.通过与PH算法的比较，说明了HABCC算法具有更小的着色方案规模，对彩色编码技术的实际应用具有重要的意义. 关键词 彩色编码；分治；核心化 中图法分类号 TP301 DOI号: 10.3724/SP.J.1016.2010.01024