30 citations · 158 across the 36 of their papers we have counts for
4 papers · 2 filters
The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
René van Bevern, Till Fluschnik, George B. Mertzios +3
This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum s-t separators, feed…
Assessing the Computational Complexity of Multi-Layer Subgraph Detection
Robert Bredereck, Christian Komusiewicz, Stefan Kratsch +3
Multi-layer graphs consist of several graphs (layers) over the same vertex set. They are motivated by real-world problems where entities (vertices) are associated via multiple type…
The Parameterized Complexity of the Minimum Shared Edges Problem
Till Fluschnik, Stefan Kratsch, Rolf Niedermeier +1
We study the NP-complete Minimum Shared Edges (MSE) problem. Given an undirected graph, a source and a sink vertex, and two integers p and k, the question is whether there are p pa…
The Minimum Shared Edges Problem on Planar Graphs
Till Fluschnik, Manuel Sorge
We study the Minimum Shared Edges problem introduced by Omran et al. [Journal of Combinatorial Optimization, 2015] on planar graphs: Planar MSE asks, given a planar graph G = (V,E)…