3 citations · 5 across the 5 of their papers we have counts for
5 papers
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…
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…
The Complexity of Finding Effectors
Laurent Bulteau, Stefan Fafianie, Vincent Froese +2
The NP-hard EFFECTORS problem on directed graphs is motivated by applications in network mining, particularly concerning the analysis of probabilistic information-propagation proce…
Streaming Kernelization
Stefan Fafianie, Stefan Kratsch
Kernelization is a formalization of preprocessing for combinatorially hard problems. We modify the standard definition for kernelization, which allows any polynomial-time algorithm…
Speeding-up Dynamic Programming with Representative Sets - An Experimental Evaluation of Algorithms for Steiner Tree on Tree Decompositions
Stefan Fafianie, Hans L. Bodlaender, Jesper Nederlof
Dynamic programming on tree decompositions is a frequently used approach to solve otherwise intractable problems on instances of small treewidth. In recent work by Bodlaender et al…