Thumbnail
Access Restriction
Subscribed

Author Brélaz, Daniel
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Graph structure ♦ Balancing ♦ Graph coloring ♦ Np-complete ♦ Comparison of the methods ♦ Scheduling
Abstract 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.
Description Affiliation: École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland (Brélaz, Daniel)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 22
Issue Number 4
Page Count 6
Starting Page 251
Ending Page 256


Open content in new tab

   Open content in new tab
Source: ACM Digital Library