Parameterized Complexity Theory

• Κύριοι συγγραφείς: Flum, Jörg (Συγγραφέας), Grohe, Martin (Συγγραφέας)
• Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
• Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
• Γλώσσα: English
• Έκδοση: Berlin, Heidelberg : Springer Berlin Heidelberg, 2006.
• Σειρά: Texts in Theoretical Computer Science. An EATCS Series
• Θέματα: Computer science.; Architecture, Computer.; Computers.; Algorithms.; Mathematical logic.; Computer Science.; Computer System Implementation.; Mathematical Logic and Foundations.; Algorithm Analysis and Problem Complexity.; Theory of Computation.; Computation by Abstract Devices.; Mathematical Logic and Formal Languages.

Parameterized complexity theory is a recent branch of computational complexity theory that provides a framework for a refined analysis of hard algorithmic problems. The central notion of the theory, fixed-parameter tractability, has led to the development of various new algorithmic techniques and a...

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

• Fixed-Parameter Tractability
• Reductions and Parameterized Intractability
• The Class W[P]
• Logic and Complexity
• Two Fundamental Hierarchies
• The First Level of the Hierarchies
• The W-Hierarchy
• The A-Hierarchy
• Kernelization and Linear Programming Techniques
• The Automata-Theoretic Approach
• Tree Width
• Planarity and Bounded Local Tree Width
• Homomorphisms and Embeddings
• Parameterized Counting Problems
• Bounded Fixed-Parameter Tractability and Limited Nondeterminism
• Subexponential Fixed-Parameter Tractability.