Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)

By J. Flum, Martin Grohe. 2006

1,225 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

VC bounds on the cardinality of nearly orthogonal function classes (2010, methodology): “/n). We will show that in this case, much of the weight of the sum is distributed among at least Ω( √ n) coeﬃcients. We will use this fact in conjunction with the standard entropy argument, see e.g., [8] to obtain the desired result. Now, we have for all i ≤ d (when n 4 ≤ d ≤ 2), n i ≤ n d < ”
Invitation to fixed-parameter algorithms (2007, background): “The earlier monograph of Downey and Fellows [2] and the contemporary one of Flum and Grohe [13] tend to be more extended in material, devoting a good part to the parameterized complexity theory.”
Fast Detection of Unsolvable Planning Instances Using Local Consistency (2013, background): “We begin by defining the basic notions of parameterised complexity theory and refer to other sources (Downey and Fellows 1999; Flum and Grohe 2006) for an in-depth treatment.”
(Meta) Kernelization (2009, methodology): “We follow the notation given in the book by Flum and Grohe [32] and add “p” in front of names of problems to emphasize that these are parameterized problems.”