Computer Science – Data Structures and Algorithms
Scientific paper
2000-09-13
Computer Science
Data Structures and Algorithms
11 pages, 7 figures. To appear in 12th ACM/SIAM Symp. Discrete Algorithms (SODA 2001). This extended abstract summarizes resul
Scientific paper
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. 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.
No associations
LandOfFree
Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction 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 Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-566902