Parameterized Complexity Theory

• Main Authors: Flum, Jörg (Author), Grohe, Martin (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: Berlin, Heidelberg : Springer Berlin Heidelberg, 2006.
• Series: Texts in Theoretical Computer Science. An EATCS Series
• Subjects: 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...