Some New Techniques in Design and Analysis of Exact (Exponential) Algorithms
Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch · 2005
This survey concerns techniques in design and analysis of algo- rithms that can be used to solve NP hard problems faster than ex- haustive search algorithms (but still in exponential time). We discuss several of such techniques: Measure & Conquer, Exponential Lower Bounds, Bounded Tree-width, and Memorization. We also consider some extensions of the mentioned techniques to parameterized algo- rithms.