1 citations · 1 across the 15 of their papers we have counts for
5 papers · 1 filter
A Faster Algorithm for Independent Cut
Vsevolod Chernyshev, Johannes Rauch, Dieter Rautenbach +1
The previously fastest algorithm for deciding the existence of an independent cut had a runtime of , where is the order of the input graph. We improve…
Cutwidth and Crossings
Johannes Rauch, Dieter Rautenbach
We provide theoretical insights around the cutwidth of a graph and the One-Sided Crossing Minimization (OSCM) problem. OSCM was posed in the Parameterized Algorithms and Computatio…
Induced Subforests and Superforests
Dieter Rautenbach, Florian Werner
Graph isomorphism, subgraph isomorphism, and maximum common subgraphs are classical well-investigated objects. Their (parameterized) complexity and efficiently tractable cases have…
Largest common subgraph of two forests
Dieter Rautenbach, Florian Werner
A common subgraph of two graphs and is a graph that is isomorphic to subgraphs of and . In the largest common subgraph problem the task is to determine a com…
On Conflict-Free Cuts: Algorithms and Complexity
Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza
One way to define the Matching Cut problem is: Given a graph , is there an edge-cut of such that is an independent set in the line graph of ? We propose the more…