Cover
Texts in Theoretical Computer Science: An EATCS Series
Exact Exponential Algorithms
Copyright
9783642165320
Preface
Acknowledgements
Contents
1 Introduction
1.1 Preliminaries
1.2 Dynamic Programming for TSP
1.3 A Branching Algorithm for Independent Set
2 Branching
2.1 Fundamentals
2.2 k-Satisfiability
2.3 Independent Set
3 Dynamic Programming
3.1 Basic Examples
3.1.1 Permutation Problems
3.1.2 Partition Problems
3.2 Set Cover and Dominating Set
3.3 TSP on Graphs of Bounded Degree
3.4 Partition into Sets of Bounded Cardinality
4 Inclusion-Exclusion
4.1 The Inclusion-Exclusion Principle
4.2 Some Inclusion-Exclusion Algorithms
4.2.1 Computing the Permanent of a Matrix
4.2.2 Directed Hamiltonian Path
4.2.3 Bin Packing
4.3 Coverings and Partitions
4.3.1 Coverings and Graph Coloring
4.3.2 Partitions
4.3.3 Polynomial Space Algorithms
4.4 Counting Subgraph Isomorphisms
5 Treewidth
5.1 Definition and Dynamic Programming
5.2 Graphs of Maximum Degree 3
5.3 Counting Homomorphisms
5.4 Computing Treewidth
5.4.1 Computing the Treewidth Using Potential Maximal Cliques
5.4.2 Counting Minimal separators and Potential Maximal Cliques
6 Measure & Conquer
6.1 Independent Set
6.2 Feedback Vertex Set
6.2.1 An Algorithm for Feedback Vertex Set
6.2.2 Computing a Minimum Feedback Vertex Set
6.3 Dominating Set
6.3.1 The Algorithm msc
6.3.2 A Measure & Conquer Analysis
6.4 Lower Bounds
7 Subset Convolution
7.1 Fast zeta Transform
7.2 Fast Subset Convolution
7.3 Applications and Variants
7.4 f-width and Rank-width
8 Local Search and SAT
8.1 Random Walks to Satisfying Assignments
8.2 Searching Balls and Cover Codes
9 Split and List
9.1 Sort and Search
9.2 Maximum Cut
10 Time Versus Space
10.1 Space for Time: Divide & Conquer
10.2 Time for Space: Memorization
11 Miscellaneous
11.1 Bandwidth
11.2 Branch & Recharge
11.3 Subexponential Algorithms and ETH
12 Conclusions, Open Problems and Further Directions
References
Appendix: Fundamental Notions on Graphs
Index