Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-033 | 29th June 1995 00:00

3-Coloring in time O(1.3446^n): a no-MIS algorithm

RSS-Feed




TR95-033
Authors: Richard Beigel, David Eppstein
Publication: 30th June 1995 16:01
Downloads: 1257
Keywords: 


Abstract:

We consider worst case time bounds for NP-complete problems
including 3-SAT, 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 [R. Floyd &
R. Beigel, The Language of Machines]. 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.



ISSN 1433-8092 | Imprint