5 citations · 13 across the 7 of their papers we have counts for
12 papers
Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration
Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch +1
An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst. 2017] for a parameterized enumeration problem consists of an algorithm that transforms each instance into…
Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch +2
Deciding whether a given graph has a square root is a classical problem that has been studied extensively both from graph theoretic and from algorithmic perspectives. The problem i…
Squares of Low Maximum Degree
Manfred Cochefert, Jean-François Couturier, Petr A. Golovach +3
A graph H is a square root of a graph G if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of decid…
A Linear Kernel for Finding Square Roots of Almost Planar Graphs
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma +1
A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are of distance 2 from each other. The Square Root p…
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs
Frank Kammer, Dieter Kratsch, Moritz Laudahn
We present space-efficient algorithms for computing cut vertices in a given graph with vertices and edges in linear time using bits. With the…
Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch
Connected Vertex Cover is one of the classical problems of computer science, already mentioned in the monograph of Garey and Johnson. Although the optimization and decision variant…