114 citations · 306 across the 50 of their papers we have counts for
Showing 2016 · cs.CCShow all
2 papers · 2 filters
cs.CC2016
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…
cs.CC2016
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…