欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
彩色编码是求解实际工程中难解问题的一种新兴而重要的技术.在应用该技术时,算法复杂度取决于彩色编码着色方案的规模,因此规模的大小将成为衡量彩色编码算法优劣的标准.彩色编码的研究在最近几年得到了许多有重要意义的结果.基于完全散列函数的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.
同期刊论文项目
同项目期刊论文
期刊信息
位置：