4 citations · 5 across the 2 of their papers we have counts for
6 papers
Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth
Falko Hegerfeld, Stefan Kratsch
We study connectivity problems from a fine-grained parameterized perspective. Cygan et al. (TALG 2022) obtained algorithms with single-exponential running time fo…
Tight algorithms for connectivity problems parameterized by clique-width
Falko Hegerfeld, Stefan Kratsch
The complexity of problems involving global constraints is usually much more difficult to understand than the complexity of problems only involving local constraints. A natural for…
Tight Bounds for Connectivity Problems Parameterized by Cutwidth
Narek Bojikian, Vera Chekan, Falko Hegerfeld +1
In this work we start the investigation of tight complexity bounds for connectivity problems parameterized by cutwidth assuming the Strong Exponential-Time Hypothesis (SETH). Van G…
Towards exact structural thresholds for parameterized complexity
Falko Hegerfeld, Stefan Kratsch
Parameterized complexity seeks to use input structure to obtain faster algorithms for NP-hard problems. This has been most successful for graphs of low treewidth: Many problems adm…
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…
On adaptive algorithms for maximum matching
Falko Hegerfeld, Stefan Kratsch
In the fundamental Maximum Matching problem the task is to find a maximum cardinality set of pairwise disjoint edges in a given undirected graph. The fastest algorithm for this pro…