114 citations · 306 across the 50 of their papers we have counts for
5 papers · 1 filter
Flow-augmentation II: Undirected graphs
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk +1
We present an undirected version of the recently introduced flow-augmentation technique: Given an undirected multigraph with distinguished vertices and an intege…
Approximate Turing Kernelization for Problems Parameterized by Treewidth
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
We extend the notion of lossy kernelization, introduced by Lokshtanov et al. [STOC 2017], to approximate Turing kernelization. An -approximate Turing kernel for a parameterized…
Optimal Discretization is Fixed-parameter Tractable
Stefan Kratsch, Tomáš Masařík, Irene Muzi +2
Given two disjoint sets and of points in the plane, the Optimal Discretization problem asks for the minimum size of a family of horizontal and vertical lines that separ…
Efficient parameterized algorithms for computing all-pairs shortest paths
Stefan Kratsch, Florian Nelles
Computing all-pairs shortest paths is a fundamental and much-studied problem with many applications. Unfortunately, despite intense study, there are still no significantly faster a…
Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space
Falko Hegerfeld, Stefan Kratsch
A breakthrough result of Cygan et al. (FOCS 2011) showed that connectivity problems parameterized by treewidth can be solved much faster than the previously best known time $\mathc…