114 citations · 306 across the 50 of their papers we have counts for
Showing 2009 · cs.CCShow all
2 papers · 2 filters
cs.CC2009★ 1 cited
Preprocessing of Min Ones Problems: A Dichotomy
Stefan Kratsch, Magnus Wahlstrom
A parameterized problem consists of a classical problem and an additional component, the so-called parameter. This point of view allows a formal definition of preprocessing: Given…
cs.CC2009
Polynomial Kernelizations for MIN F^+Pi_1 and MAX NP
Stefan Kratsch
It has been observed in many places that constant-factor approximable problems often admit polynomial or even linear problem kernels for their decision versions, e.g., Vertex Cover…