1 citations · 1 across the 11 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
cs.DS2023
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…
cs.DS2023
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…
math.CO2023
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…