Title:
Fundamentals of Parameterized Complexity by Rodney G. Downey, Michael R. Fellows.
Texts in Computer Science,
Texts in computer science,
Main Entry:
Downey, Rodney G. author.
Fellows, Michael R. author.
SpringerLink (Online service)
Publisher:
Springer London : Imprint: Springer,
Publication Date:
2013.
Publication Place:
London :
ISBN:
9781447155591
Subject:
Computer science.
Computer software.
Computer science.
Algorithm Analysis and Problem Complexity.
Mathematics of Algorithmic Complexity.
Series:
Texts in Computer Science,
Texts in computer science,
Contents:
Introduction -- Part I: Parameterized Tractability -- Preliminaries -- The Basic Definitions -- Part II: Elementary Positive Techniques -- Bounded Search Trees -- Kernelization -- More on Kernelization -- Iterative Compression, and Measure and Conquer, for Minimization Problems -- Further Elementary Techniques -- Colour Coding, Multilinear Detection, and Randomized Divide and Conquer -- Optimization Problems, Approximation Schemes, and Their Relation to FPT -- Part III: Techniques Based on Graph Structure -- Treewidth and Dynamic Programming -- Heuristics for Treewidth -- Automata and Bounded Treewidth -- Courcelle's Theorem -- More on Width-Metrics: Applications and Local Treewidth -- Depth-First Search and the Plehn-Voigt Theorem -- Other Width Metrics -- Part IV: Exotic Meta-Techniques -- Well-Quasi-Orderings and the Robertson-Seymour Theorems -- The Graph Minor Theorem -- Applications of the Obstruction Principle and WQOs -- Part V: Hardness Theory -- Reductions -- The Basic Class W[1] and an Analog of Cook's Theorem -- Other Hardness Results -- The W-Hierarchy -- The Monotone and Antimonotone Collapses -- Beyond W-Hardness -- k-Move Games -- Provable Intractability: The Class XP -- Another Basis -- Part VI: Approximations, Connections, Lower Bounds -- The M-Hierarchy, and XP-optimality -- Kernelization Lower Bounds -- Part VII: Further Topics -- Parameterized Approximation -- Parameterized Counting and Randomization -- Part VIII: Research Horizons -- Research Horizons -- Part IX Appendices -- Appendix 1: Network Flows and Matchings -- Appendix 2: Menger's Theorems.
Related Records:
Springer eBooks
Printed edition: 9781447155584
Cover Image:
Log in
Help
