1 citations · 1 across the 11 of their papers we have counts for
6 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…
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.
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…