Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Improving the performance guarantee for approximate graph coloring
Wigderson A. Journal of the ACM30 (4):729-735,1983.Type:Article
Date Reviewed: Feb 1 1985

A graph coloring algorithm makes an assignment of colors to the vertices of a graph so that each vertex is of a different color than its neighbors. The chromatic number of a graph is the least number of colors for which such an assignment can be made. The performance guarantee of a graph coloring algorithm is the worst case ratio between the number of colors it assigns to a graph and that graph’s chromatic number. In 1974, Johnson [1] showed that the Greedy Independent Set algorithm for coloring ran in time O(n2) with performance guarantee O(n/log n) for all graphs. Wigderson improves upon the results of Johnson in several ways.

First, an algorithm is given that colors any graph on n vertices with known chromatic number k in linear time with at most 2k :9I colors. This algorithm is extended and combined with the Greedy Independent Set algorithm to produce an algorithm running in O(n2) time with performance guarantee of O(n(log log n)2/(log n)2).

Reviewer:  W. B. Poucher Review #: CR109067
1) Johnson, D. S.Worst case behavior or graph coloring algorithms, in Proc. 5th South-Eastern conf. on combinatorics, graph theory and computing, Utilitas Mathematica Publ., Winnipeg, Manitoba, Canada, 1974, 513–528.
Bookmark and Share
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
 
Graph Algorithms (G.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Nonnumerical Algorithms And Problems": Date
Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra
Demel J., Demlová M., Koubek V. Theoretical Computer Science 36(2-3): 203-216, 1985. Type: Article
Jan 1 1986
Complexity of the word problem for commutative semigroups of fixed dimension
Huynh D. Acta Informatica 22(4): 421-432, 1985. Type: Article
May 1 1986
Calculation of Minkowski-reduced lattice bases
Afflerbach L., Grothe H. Computing 35(3-4): 269-276, 1985. Type: Article
Aug 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy