Title :
3-coloring in time 0(1.3446n): a no-MIS algorithm
Author :
Beigel, Richard ; Eppstein, David
Author_Institution :
Dept. of Comput. Sci., Yale Univ., New Haven, CT, USA
Abstract :
We consider worst case time bounds for NP-complete problems including 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a common generalization of these problems, called symbol-system satisfiability or, briefly, SSS. 3-SAT is equivalent to (2,3)-SSS while the other problems above are special cases of (3,2)-SSS; there is also a natural duality transformation from (a,b)-SSS to (b,a)-SSS. We give a fast algorithm for (3,2)-SSS and use it to improve the time bounds for solving the other problems listed above
Keywords :
computability; computational complexity; decidability; duality (mathematics); graph colouring; 3-SAT; 3-coloring; 3-edge-coloring; 3-list-coloring; NP-complete problems; common generalization; duality transformation; symbol-system satisfiability; time bounds; worst case time bounds; Computer science; NP-complete problem; Polynomials; Search problems; Testing;
Conference_Titel :
Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on
Conference_Location :
Milwaukee, WI
Print_ISBN :
0-8186-7183-1
DOI :
10.1109/SFCS.1995.492575
