Fundamentals of Parameterized Complexity

• Κύριοι συγγραφείς: Downey, Rodney G. (Συγγραφέας), Fellows, Michael R. (Συγγραφέας)
• Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
• Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
• Γλώσσα: English
• Έκδοση: London : Springer London : Imprint: Springer, 2013.
• Σειρά: Texts in Computer Science,
• Θέματα: Computer science.; Algorithms.; Computer Science.; Algorithm Analysis and Problem Complexity.; Mathematics of Algorithmic Complexity.

The field of parameterized complexity/multivariate complexity algorithmics is an exciting and vibrant part of theoretical computer science, responding to the vital need for efficient algorithms in modern society. This comprehensive and self-contained textbook presents an accessible overview of the s...

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

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