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