Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction
| dc.creator | Eppstein, David | |
| dc.date | 2000-09-13 | |
| dc.date.accessioned | 2026-07-07T03:16:32Z | |
| dc.date.available | 2026-07-07T03:16:32Z | |
| dc.description | 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. | |
| dc.description | 11 pages, 7 figures. To appear in 12th ACM/SIAM Symp. Discrete Algorithms (SODA 2001). This extended abstract summarizes results from cs.DS/0006046 "3-coloring in time O(1.3289^n)" (with Richard Beigel) that were found after our FOCS 1995 paper on the same subject | |
| dc.identifier | https://arxiv.org/abs/cs/0009006 | |
| dc.identifier | http://arxiv.org/abs/cs/0009006 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30388 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | F.2.2 | |
| dc.title | Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction | |
| dc.type | text |