next up previous contents index CD CD Algorithms
Next: Hamiltonian Cycles Up: Intractable Problems and Approximations Previous: Problems and Reductions

Simple Reductions

Since they can be used either to prove hardness or to give efficient algorithms, reductions are powerful tools for the algorithm designer to be familiar with. The best way to understand reductions is to look at some simple ones.

Mon Jun 2 23:33:50 EDT 1997