PARAMETERIZED COMPLEXITY THEORY
2006pp. 205–236
Citations Over TimeTop 1% of 2006 papers
Abstract
Abstract This chapter offers a closer look at parameterized computational complexity theory. Central concepts in this context are parameterized problems, parameterized reducibility, parameterized complexity classes, W[1], complete problems, and W[1]-hardness proofs. In addition, the chapter provides a survey of some recent developments concerning structural parameterized complexity theory.
Related Papers
- → SPIKE: A system for sufficient completeness and parameterized inductive proofs(1994)11 cited
- → Sufficient completeness and parameterized proofs by induction(1994)3 cited
- Parameterized conditional specifications : sufficient completeness and implicit induction(1993)
- → Structure and Specification as Sources of Complexity(2009)
- Parameterized Computation and Complexity： A New Approach Dealing with NP-Hardness(2005)