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

R. Beigel and D. Eppstein.

Tech. Rep. 95-033, Electronic Coll. Computational Complexity, 1995.

*36th IEEE Symp. Foundations of Comp. Sci.*, 1995, pp. 444–453.

DIMACS Worksh. Faster Exact Solutions for NP-Hard Problems, 2000.Speeds up 3-coloring by solving a harder problem: constraint satisfaction in which each variable can take on one of three values and each constraint forbids a pair of variable assignments. The detailed solution involves several long hairy case analyses. Similar methods apply also to 3-list-coloring, 3-edge-coloring, and 3-SAT. The 3-SAT algorithm is fixed-parameter tractible in that it is polynomial time when the number of 3-variable clauses is O(log n). Merged into 3-coloring in time O(1.3289^n) for the journal version.

(DIMACS abstract and slides)

Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.