Exact Exponential Algorithms

• Main Authors: Fomin, Fedor V. (Author), Kratsch, Dieter. (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic
• Language: English
• Published: Berlin, Heidelberg : Springer Berlin Heidelberg, 2010.
• Series: Texts in Theoretical Computer Science. An EATCS Series,
• Subjects: Computer science.; Computer software.; Combinatorics.; Mathematical optimization.; Computer Science.; Algorithm Analysis and Problem Complexity.; Optimization.
• Online Access: https://ezaccess.library.uitm.edu.my/login?url=http://dx.doi.org/10.1007/978-3-642-16533-7

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:

• Introduction
• 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
• References
• Appendix  Graphs
• Index.