Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
3-coloring in time O(1.3289)
Beigel R., Eppstein D. Journal of Algorithms54 (2):168-204,2005.Type:Article
Date Reviewed: Jul 5 2005

The main result of this paper is a proof that the three-coloring problem can be solved in worst-case time O(1.3289n). The previous record for this problem was the O(1.415n) result of Schiermeyer [1]. The proof is based on the interesting idea that it is sufficient to constrain the problem by restricting each vertex to two of the three colors, since such a constraint problem can be solved in polynomial (P) time as an instance of 2-satisfiability (2-SAT). A simple application of this idea already produces an O(1.5n) time-randomized algorithm.

Reviewer:  D. Seese Review #: CR131450 (0512-1348)
1) Schiermeyer, I. Deciding 3-colorability in less than O(1.415n) steps. In Proc. 19th Int. Workshop on Graph-Theoretic Concepts in Computer Science (LNCS 790) Springer-Verlag, 1994, 177–182.
Bookmark and Share
 
Graph Algorithms (G.2.2 ... )
 
 
Graph Labeling (G.2.2 ... )
 
 
Graph Theory (G.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Algorithms": Date
Planar graph decomposition and all pairs shortest paths
Frederickson G. (ed) Journal of the ACM 38(1): 162-204, 1991. Type: Article
Oct 1 1991
High probability parallel transitive-closure algorithms
Ullman J., Yannakakis M. SIAM Journal on Computing 20(1): 100-125, 1991. Type: Article
Dec 1 1991
Clique partitions, graph compression and speeding-up algorithms
Feder T., Motwani R.  Theory of computing (, New Orleans, LA, May 6-8, 1991)1331991. Type: Proceedings
Oct 1 1992
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