Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > DAVID EPPSTEIN:
All reports by Author David Eppstein:

TR95-033 | 29th June 1995
Richard Beigel, David Eppstein

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

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 ... more >>>




ISSN 1433-8092 | Imprint