Exact Exponential Algorithms

• Κύριοι συγγραφείς: Fomin, Fedor V. (Συγγραφέας), Kratsch, Dieter (Συγγραφέας)
• Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
• Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
• Γλώσσα: English
• Έκδοση: Berlin, Heidelberg : Springer Berlin Heidelberg, 2010.
• Σειρά: Texts in Theoretical Computer Science. An EATCS Series,
• Θέματα: 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?...

Πίνακας περιεχομένων:

• 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.