基于遗传算法的图关联着色算法

• 作者: 刘西奎 李艳 许进
• 来源期刊: 工程数学学报
• 学科: 工学
• 关键词: 关联着色 关联色数 关联图 遗传算法
• 年，卷（期）: 2004,（1）
• 页码范围: 41-47
• 页数: 7页
• 分类号: O157.05C|TP3
• 字数: 5086字
• 语种: 中文
• DOI: 10.3969/j.issn.1005-3085.2004.01.007

摘要

图的着色算法是一种典型的NP-完全问题.给出了一种用于图的关联着色的遗传算法.遗传算法用于进行全局搜索,从而有效的查找解空间.文中对关联色数为6的一个图进行了仿真实验,给出了该图的关联色数以及4种6-关联着色.用本文提出的算法,得到了完全图、完全多部图的关联色数.实验结果表明,本文设计的遗传算法可以很好的对关联着色猜想进行求解,获得问题的高质量的解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许进	华中科技大学控制科学与工程系	117	2149	25.0	39.0
2	刘西奎	山东科技大学信息科学与工程学院	9	106	7.0	9.0
6	李艳	山东科技大学信息科学与工程学院	12	62	5.0	7.0