6 papers
Degenerate Vertex Cuts in Sparse Graphs
Thilo Hartel, Johannes Rauch, Dieter Rautenbach
For a non-negative integer , a vertex cut in a graph is -degenerate if it induces a -degenerate subgraph. We show that a graph of order at least without a -d…
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…
GridOT -- a discrete optimal transport solver on grids
Johannes Rauch, Leo Zanotti
We provide an improved implementation of Schmitzer's sparse multi-scale algorithm for discrete optimal transport on grids. We report roughly 2-4 times faster runtimes on the DOTmar…
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…
weberknecht -- a One-Sided Crossing Minimization solver
Johannes Rauch
We describe the implementation of the exact solver weberknecht and the heuristic solver weberknecht_h for the One-Sided Crossing Minimization problem.
Revisiting Extremal Graphs Having No Stable Cutsets
Johannes Rauch, Dieter Rautenbach
Confirming a conjecture posed by Caro, it was shown by Chen and Yu that every graph with vertices and at most edges has a stable cutset, which is a stable set of ver…