Invitation to Fixed-Parameter Algorithms

• Covers the most recent ideas and concepts in the developing area of fixed-parameter algorithms
• Growing and highly topical area
• Numerous real-life case studies
• Aimed at graduate and research mathematicians, programmers, algorithm designers, and computer scientists

Readership: Graduate and research mathematicians, programmers, algorithm designers, and computer scientists

Rolf Niedermeier, Universitaet Jena

"You will enjoy reading it whether you want to do research in the area or just want to learn about it. And while merily intending the latter, you are most likely going to end up doing the former when you finish reading it." - EMS Newsletter

"This book is an excellent introduction to the algorithmic aspects of the field" - William Gasarch and Kin Keung Ma, The Computer Journal, Vol. 51 No. 1

"Niedermeier presents a wider range of concrete problems and pronlem variants, highlighting many algorithmic tricks and applications." - Daniel Marx, Mathematical Review

Part I: Foundations
1: Introduction to Fixed-Parameter Algorithms
2: Preliminaries and Agreements
3: Parameterized Complexity Theory - A Primer
4: Vertex Cover - An Illustrative Example
5: The Art of Problem Parameterization
6: Summary and Concluding Remarks
Part II: Algorithmic Methods
7: Data Reduction and Problem Kernels
8: Depth-Bounded Search Trees
9: Dynamic Programming
10: Tree Decompositions of Graphs
11: Further Advanced Techniques
12: Summary and Concluding Remarks
Part III: Some Theory, Some Case Studies
13: Parameterized Complexity Theory
14: Connections to Approximation Algorithms
15: Selected Case Studies
16: Zukunftsmusik
References
Index