8 citations · 14 across the 8 of their papers we have counts for
3 papers · 1 filter
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…
Induced Disjoint Paths in Circular-Arc Graphs in Linear Time
Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen
The Induced Disjoint Paths problem is to test whether a graph G with k distinct pairs of vertices (s_i,t_i) contains paths P_1,...,P_k such that P_i connects s_i and t_i for i=1,..…
Obtaining Planarity by Contracting Few Edges
Petr A. Golovach, Pim van 't Hof, Daniel Paulusma
The Planar Contraction problem is to test whether a given graph can be made planar by using at most k edge contractions. This problem is known to be NP-complete. We show that it is…