David Eppstein – Publications

Publications with Richard Beigel

• 3-Coloring in time O(1.3446ⁿ): a no-MIS algorithm.
  R. Beigel and D. Eppstein.
  Tech. Rep. 95-033, Electronic Coll. Computational Complexity, 1995.
  36th IEEE Symp. Foundations of Comp. Sci., 1995, pp. 444–453.
  DIMACS Worksh. Faster Exact Solutions for NP-Hard Problems, 2000.

  Speeds up 3-coloring by solving a harder problem: constraint satisfaction in which each variable can take on one of three values and each constraint forbids a pair of variable assignments. The detailed solution involves several long hairy case analyses. Similar methods apply also to 3-list-coloring, 3-edge-coloring, and 3-SAT. The 3-SAT algorithm is fixed-parameter tractible in that it is polynomial time when the number of 3-variable clauses is O(log n). Merged into 3-coloring in time O(1.3289^n) for the journal version.

  (DIMACS abstract and DIMACS slides)

• 3-coloring in time O(1.3289^n).
  R. Beigel and D. Eppstein.
  arXiv:cs.DS/0006046.
  J. Algorithms 54:2 (2005) 168-204.

  Journal paper combining 3-coloring algorithms from our FOCS '95 paper with improved bounds from our SODA '01 paper.