| 一种在元素与颜色规模相近时的有效着色算法及其应用 |
| |
| 引用本文： | 王建新,刘云龙,陈建二.一种在元素与颜色规模相近时的有效着色算法及其应用[J].计算机学报,2008,31(1):32-42. |
| |
| 作者姓名： | 王建新 刘云龙 陈建二 |
| |
| 作者单位： | 中南大学信息科学与工程学院,长沙,410083 |
| |
| 基金项目： | 国家自然科学基金重点项目“生物信息学中的相关组合理论和算法研究”(60433020)，国家自然科学基金(60773111)，湖南省杰出青年基金(06JJ10009)，新世纪优秀人才支持计划(NCET-05-0683)，国家教育部创新团队资助计划(IRT0661)资助 |
| |
| 摘 要： | 着色算法(color-coding)是求解NP难问题的重要手段之一.而在应用着色算法时,着色算法所产生的着色方案的规模极大地影响着问题的求解性能,故构造一个尽可能小的着色方案是着色算法所寻求的目标.目前存在的着色算法均基于完全散列函数,并要求元素数目n远大于颜色数目k,且k比较小,这个限制条件使得这些着色算法在一些实际情况下无法应用.该文主要研究在元素与颜色规模相近时(n2k)的有效着色算法,并着重分析在n2k情况下着色算法的性能.该文提出了一种基于划分思想的着色方案构造算法PBCC,证明了由PBCC产生的着色方案确实可以覆盖到所有的子集,并具体给出了可应用于(l,d)-(20,16)Motif查找问题的403种着色的构造方法.文章进一步分析了PBCC产生的着色方案规模,并证明了在n2k且n-k2的情况下,任何着色算法所产生的着色方案的规模|S(n,k)|都不小于n/2 n-k] n n-k]-n/2 n-k]2~(n-k)]/(2~(n-k)-2).此外,文中也采用了渐进分析技术,证明了PBCC算法生成着色方案规模为O(e2Rootof(ex-eμx 1)(n-k)),在n=2k的情况下结果是O(2.62n-k);同时,文中也证明了n2k情况下着色方案规模的下界为2n-k.
|
| 关 键 词： | 着色 着色算法 NP难问题 渐进分析 界限分析 |
| 收稿时间： | 2006-08-24 |
| 修稿时间： | 2007-09-06 |
An Effective Coloring Algorithm for Close Relationship Between the Scales of Element Set and Color Set and Its Application |
| |
| WANG Jian-Xin,LIU Yun-Long,CHEN Jian-Er.An Effective Coloring Algorithm for Close Relationship Between the Scales of Element Set and Color Set and Its Application[J].Chinese Journal of Computers,2008,31(1):32-42. |
| |
| Authors: | WANG Jian-Xin LIU Yun-Long CHEN Jian-Er |
| |
| Abstract: | |
| |
| Keywords: | coloring coloring algorithm NP-hard asymptotic analysis bound analysis |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
