114 citations · 385 across the 36 of their papers we have counts for
Showing 2010Show all
2 papers · 1 filter
cs.CC2010★ 114 cited
Cross-Composition: A New Technique for Kernelization Lower Bounds
Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
We introduce a new technique for proving kernelization lower bounds, called cross-composition. A classical problem L cross-composes into a parameterized problem Q if an instance of…
cs.DS2010★ 94 cited
Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter
Bart M. P. Jansen, Hans L. Bodlaender
An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G',…