ICS Theory Group

ICS 280, Fall 2000: Exponential Algorithms
Course Readings and Useful References

Surveys and Collections

DIMACS Worksh. Faster Exact Solutions for NP-Hard Problems (many good papers).

SAT: references on satisfiability.

O. Kullmann papers, links, and software for the SAT problem.

V. Kumar. Algorithms for Constraint-Satisfaction Problems: A Survey. AI Magazine 13(1):32-44, 1992.
For more general references on constraint satisfaction, see The Constraints Archive.

Specific Algorithms

E. Dantsin, A. Goerdt, E. A. Hirsch, and U. Schöning. Deterministic algorithms for k-SAT based on covering codes and local search. Proc. 27th Int. Coll. Automata, Languages and Programming, 2000.

U. Schöning. A probabliistic algorithm for $k$-SAT and constraint satisfaction problems. Proc. 40th Symp. Foundations of Computer Science, IEEE, October 1999, pp. 410--414. (Hardcopy is in graduate filing cabinet, CS building 4th floor elevator lobby near coffee room.)

D. Eppstein and R. Beigel. 3-coloring in time O(1.3289^n). (See this extended abstract for a gentler introduction.)

D. Eppstein. Small maximal independent sets and faster exact graph coloring.

Systematic Generation of Very Hard Cases for Graph 3-Colorability, R. Vlasie.

Concorde: a code for solving traveling salesman problems.

D. M. Warme, P. Winter, and M. Zachariasen. Exact solutions to large-scale plane Steiner tree problems.

Practical application of large-scale exponential search in optimizing fast software encryption code