114 citations · 306 across the 50 of their papers we have counts for
Showing 2015 · cs.DSShow all
3 papers · 2 filters
cs.DS2015
A randomized polynomial kernel for Subset Feedback Vertex Set
Eva-Maria C. Hols, Stefan Kratsch
The Subset Feedback Vertex Set problem generalizes the classical Feedback Vertex Set problem and asks, for a given undirected graph , a set , and an integer…
cs.DS2015★ 1 cited
Preprocessing under uncertainty
Stefan Fafianie, Stefan Kratsch, Voung Anh Quyen
In this work we study preprocessing for tractable problems when part of the input is unknown or uncertain. This comes up naturally if, e.g., the load of some machines or the conges…
cs.DS2015★ 1 cited
A shortcut to (sun)flowers: Kernels in logarithmic space or linear time
Stefan Fafianie, Stefan Kratsch
We investigate whether kernelization results can be obtained if we restrict kernelization algorithms to run in logarithmic space. This restriction for kernelization is motivated by…