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

• 作者: 刘云龙 杨志彪 王建新 陈建二
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 彩色编码 分治 核心化
• 年，卷（期）: 2010,（6）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 1024-1031
• 分类号: TP301
• 字数: 8527字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2010.01024

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王建新	中南大学信息科学与工程学院	371	3185	23.0	39.0
2	陈建二	中南大学信息科学与工程学院	167	1535	20.0	30.0
3	刘云龙	中南大学信息科学与工程学院	23	75	5.0	7.0
4	杨志彪	中南大学信息科学与工程学院	2	13	1.0	2.0