3-Coloring in Time O(1.3289^n)

Details 3-Coloring in Time O(1.3289^n) 3-Coloring in Time O(1.3289^n)

2000-06-30

arxiv.org/abs/cs/0006046v1

J. Algorithms 54:2 (2005) 168-204

Computer Science

Data Structures and Algorithms

31 pages, 22 figures. An earlier version of this paper was presented at the 36th IEEE Symp. Foundations of Comp. Sci., 1995, a

Scientific paper

10.1016/j.jalgor.2004.06.008

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.

Affiliated with

Also associated with

No associations

Rating

3-Coloring in Time O(1.3289^n) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with 3-Coloring in Time O(1.3289^n), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 3-Coloring in Time O(1.3289^n) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-528646