4 citations · 8 across the 3 of their papers we have counts for
4 papers · 1 filter
Efficient parameterized algorithms on graphs with heterogeneous structure: Combining tree-depth and modular-width
Stefan Kratsch, Florian Nelles
Many computational problems admit fast algorithms on special inputs, however, the required properties might be quite restrictive. E.g., many graph problems can be solved much faste…
On Triangle Counting Parameterized by Twin-Width
Stefan Kratsch, Florian Nelles, Alexandre Simon
In this report we present an algorithm solving Triangle Counting in time , where n and m, respectively, denote the number of vertices and edges of a graph G and d denote…
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…
Efficient and adaptive parameterized algorithms on modular decompositions
Stefan Kratsch, Florian Nelles
We study the influence of a graph parameter called modular-width on the time complexity for optimally solving well-known polynomial problems such as Maximum Matching, Triangle Coun…