基于三角环的顶点着色问题解法

• 作者: 王元珍 龚卫华
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: NP完全问题 三角环 极大独立集
• 年，卷（期）: 2005,（4）
• 所属期刊栏目: 人工智能与图像处理技术
• 页码范围: 77-78,93
• 页数: 3页
• 分类号: TP3
• 字数: 2890字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2005.04.024

摘要

图的着色问题是一个NP难问题,本文着重探讨无向图的顶点的三色问题,提出了用构造三角环的极大独立集方法判断并尝试给出顶点三色问题的可行解,解决了顶点三色的可满足性问题,克服了以前图遍历过程中的回溯问题,以及由此推论顶点四色和五色问题的极大独立集.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王元珍	华中科技大学计算机学院	86	1120	18.0	30.0
2	龚卫华	华中科技大学计算机学院	5	16	2.0	3.0