NEW METHODS TO COLOR THE VERTICES OF A GRAPH

被引：917

作者：

BRELAZ, D

机构：

[1] École Polytechnique Fédérale de Lausanne, Département de Mathématiques, 1007 Lausanne

来源：

COMMUNICATIONS OF THE ACM | 1979年 / 22卷 / 04期

关键词：

balancing; comparison of the methods; graph coloring; graph structure; NP-complete; scheduling;

D O I：

10.1145/359094.359101

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper describes efficient new heuristic methods to color the vertices of a graph which rely upon the comparison of the degrees and structure of a graph. A method is developed which is exact for bipartite graphs and is an important part of heuristic procedures to find maximal cliques in general graphs. Finally an exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs, and the new heuristic methods, the classical methods, and the exact method are compared. © 1979, ACM. All rights reserved.

引用

页码：251 / 256

页数：6