Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction

David Eppstein
Proc. 12th Symp. Discrete Algorithms, ACM and SIAM, Jan 2001, pp. 329–337
ACM Computing Research Repository, cs.DS/0009006

Cited by:

• Algorithms for quantified Boolean formulas
• 3-colorability $\in\cal{P}$ for $P_6$-free graphs
• On the number of maximal independent sets in a graph
• Algorithms for $k$-colouring and finding maximal independent sets
• Exact algorithms for NP-hard problems: A survey
• Finite domain constraint satisfaction using quantum computation
• Worst-case time bounds for coloring and satisfiability problems
• 3-SAT $\in RTIME(O(1.32793^n))$: Improving randomized local search by initializing strings of 3-clauses
• Determining the number of solutions to binary CSP instances
• It is tough to be a plumber
• Enumerating maximal independent sets with applications to graph colouring