摘要
在点着色问题中，引入了一种新方法，即使用补图和团覆盖的概念解决繁杂的点着色问题．它比普通的加边缩边法和纵深搜索法更为简便，在一定程度上降低了运算复杂度．该算法本身简洁明了，既适于比较简单的图，又适用于比较复杂的图．同时，文中还给出了与团覆盖对应的独立集结构的算法及其复杂度估算．
In this paper,a new method of using the complement graph and clique covering to solvethe complex vertex coloring problem is introduced,which is much simpler than the commonadd-decrease edges and DFS algorithms. It also reduces the computing complexity.The algo-rithm is simple,but it is suitable for the simple graph and the large graph.An independent-setstructure algorithm which is related with the clique covering is given.
出处
《西安电子科技大学学报》
EI
CAS
CSCD
北大核心
1995年第4期454-457,共4页
Journal of Xidian University
关键词
点着色
补图
团覆盖
算法
vertex coloring
complement graph
clique covering
algorithm
