Exact Exponential Algorithms
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?...
| Main Authors: | , |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
2010, 2010
|
| Edition: | 1st ed. 2010 |
| Series: | Texts in Theoretical Computer Science. An EATCS Series
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer eBooks 2005- - Collection details see MPG.ReNa |
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