1 citations · 1 across the 11 of their papers we have counts for
11 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…
Forest Cuts in Sparse Graphs
Vsevolod Chernyshev, Johannes Rauch, Dieter Rautenbach
We propose the conjecture that every graph of order with less than edges has a vertex cut that induces a forest. Maximal planar graphs do not have such vertex cuts a…
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…
Exact and Parameterized Algorithms for the Independent Cutset Problem
Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza
The Independent Cutset problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. Such a problem is -complete even when th…
Sparse vertex cutsets and the maximum degree
Stéphane Bessy, Johannes Rauch, Dieter Rautenbach +1
We show that every graph of maximum degree and sufficiently large order has a vertex cutset of order at most that induces a subgraph of maximum degree at mos…
Efficiently recognizing graphs with equal independence and annihilation numbers
Johannes Rauch, Dieter Rautenbach
The annihilation number of a graph is an efficiently computable upper bound on the independence number of . Recently, Hiller observed that a characterization o…