| 一种基于混合策略的彩色编码算法 |
| |
| 引用本文： | 王建新,杨志彪,刘云龙,陈建二.一种基于混合策略的彩色编码算法[J].计算机学报,2010,33(6). |
| |
| 作者姓名： | 王建新 杨志彪 刘云龙 陈建二 |
| |
| 作者单位： | 中南大学信息科学与工程学院,长沙,410083 |
| |
| 基金项目： | 国家自然科学基金(60773111);;国家“九七三”重点基础研究发展规划项目前期研究专项(2008CB317107);;高等学校博士学科点专项科研基金项目(20090162110056);;国家教育部创新团队资助计划(IRT0661)资助~~ |
| |
| 摘 要： | 彩色编码是求解实际工程中难解问题的一种新兴而重要的技术.在应用该技术时,算法复杂度取决于彩色编码着色方案的规模,因此规模的大小将成为衡量彩色编码算法优劣的标准.彩色编码的研究在最近几年得到了许多有重要意义的结果.基于完全散列函数的PH算法产生的着色方案规模为O*(6.1kn),是目前世界上最好的确定彩色编码结果;彩色编码算法PBCC是一种利用组合思想针对n 2k的有效着色算法.文中以分治算法为基础,结合核心化技术,并利用PBCC算法求解子问题,提出了一种基于混合策略的彩色编码算法HABCC,并且证明了由HABCC算法产生的着色方案确实可以覆盖到所有子集,着色方案规模为|S(n,k)|2k.logkk-1.n.通过与PH算法的比较,说明了HABCC算法具有更小的着色方案规模,对彩色编码技术的实际应用具有重要的意义.
|
| 关 键 词： | 彩色编码 分治 核心化 |
An Improved Color Coding Algorithm Based on Hybrid Architecture |
| |
| WANG Jian-Xin,YANG Zhi-Biao,LIU Yun-Long,CHEN Jian-Er.An Improved Color Coding Algorithm Based on Hybrid Architecture[J].Chinese Journal of Computers,2010,33(6). |
| |
| Authors: | WANG Jian-Xin YANG Zhi-Biao LIU Yun-Long CHEN Jian-Er |
| |
| Affiliation: | School of Information Science and Engineering/a>;Central South University/a>;Changsha 410083 |
| |
| 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(Parti... |
| |
| Keywords: | color coding divide-and-conquer kernelization |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
