| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | 基于粘贴和删除系统的图着色问题分析 |
| 作者 | 王淑栋 |
| 作者单位 | (山东科技大学信息科学与工程学院 山东青岛 266510) (北京大学信息科学技术学院软件所 北京 100871) |
| 发表年份 | 2008 |
| 发表月份 | 12期(2123—2128) |
| 文章摘要 | 摘要 图着色问题是图与组合优化中的一个NP-完全问题.现有算法在求解图着色问题时，计算复杂性随着待解问题规模的增大呈指数增长.粘贴系统和删除系统是分别基于粘贴运算和删除运算的两种语言生成器.文中将图着色问题和图的坏边数结合起来，将图着色问题转化成搜索最长序列的问题，然后利用粘贴系统和删除系统的并行性，得到了图的色数及其所有色类.与已有求解图着色问题的DNA算法相比，新的算法具有较低的复杂性. 关键词 DNA计算；图着色；粘贴和删除系统；坏边 |