Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction
<|reference_start|>Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction: 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.<|reference_end|>
@article{eppstein2000improved,
    title={Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint
  Satisfaction},
    author={David Eppstein},
    journal={arXiv preprint arXiv:cs/0009006},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0009006},
    primaryClass={cs.DS}
}