3-Coloring in Time O(1.3289^n)
3-Coloring in Time O(1.3289^n)
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 constraint satisfaction (CSP) formulation of these problems. 3-SAT is equivalent to (2,3)-CSP while the other problems above are special cases of (3,2)-CSP; there is also a natural duality transformation from (a,b)-CSP to (b,a)-CSP. We give a fast algorithm for (3,2)-CSP and use it to improve the time bounds for solving the other problems listed above. Our techniques involve a mixture of Davis-Putnam-style backtracking with more sophisticated matching and network flow based ideas.
31 pages, 22 figures. An earlier version of this paper was presented at the 36th IEEE Symp. Foundations of Comp. Sci., 1995, and appears as ECCC TR 95-033
- University of California, Irvine United States
- Yale University United States
\(H\)-distance, FOS: Computer and information sciences, Analysis of algorithms and problem complexity, Girsanov theorem, Heat measures, Loop groups, Coloring of graphs and hypergraphs, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Data Structures and Algorithms (cs.DS), Wasserstein distance, F.2.2, Nonnumerical algorithms, Constraint Satisfaction
\(H\)-distance, FOS: Computer and information sciences, Analysis of algorithms and problem complexity, Girsanov theorem, Heat measures, Loop groups, Coloring of graphs and hypergraphs, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Data Structures and Algorithms (cs.DS), Wasserstein distance, F.2.2, Nonnumerical algorithms, Constraint Satisfaction
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!