基于粘贴和删除系统的图着色问题分析

• 作者: 王淑栋
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: DNA计算 图着色 粘贴和删除系统 坏边
• 年，卷（期）: 2008,（12）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 2123-2128
• 页数: 6页
• 分类号: TP301
• 字数: 1607字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2008.12.008

摘要

图着色问题是图与组合优化中的一个NP-完全问题.现有算法在求解图着色问题时,计算复杂性随着待解问题规模的增大呈指数增长.粘贴系统和删除系统是分别基于粘贴运算和删除运算的两种语言生成器.文中将图着色问题和图的坏边数结合起来,将图着色问题转化成搜索最长序列的问题,然后利用粘贴系统和删除系统的并行性,得到了图的色数及其所有色类.与已有求解图着色问题的DNA算法相比,新的算法具有较低的复杂性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王淑栋	山东科技大学信息科学与工程学院	30	316	10.0	17.0