1 citations · 1 across the 12 of their papers we have counts for
15 papers
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…
An Optimization Approach to Degree Deviation and Spectral Radius
Dieter Rautenbach, Florian Werner
For a finite, simple, and undirected graph with vertices and average degree , Nikiforov introduced the degree deviation of as $s=\sum_{u\in V(G)}\left|d_G(u)-d\right…
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…
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…