Exact Exponential Algorithms

• Main Authors: Fomin, Fedor V. (Author), Kratsch, Dieter (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: Berlin, Heidelberg : Springer Berlin Heidelberg, 2010.
• Series: Texts in Theoretical Computer Science. An EATCS Series,
• Subjects: Mathematics.; Computer programming.; Algorithms.; Mathematical optimization.; Discrete mathematics.; Combinatorics.; Discrete Mathematics.; Optimization.; Programming Techniques.; Algorithm Analysis and Problem Complexity.

Today most computer scientists believe that NP-hard problems cannot be solved by polynomial-time algorithms. From the polynomial-time perspective, all NP-complete problems are equivalent but their exponential-time properties vary widely. Why do some NP-hard problems appear to be easier than others?...

Table of Contents:

• Branching
• Dynamic Programming
• Inclusion-Exclusion
• Treewidth
• Measure & Conquer
• Subset Convolution
• Local Search and SAT
• Split and List
• Time Versus Space
• Miscellaneous
• Conclusions, Open Problems and Further Directions.