25 citations · 109 across the 80 of their papers we have counts for
7 papers · 2 filters
Editing to a Graph of Given Degrees
Petr A. Golovach
We consider the Editing to a Graph of Given Degrees problem that asks for a graph G, non-negative integers d,k and a function δ:V(G)->{1,...,d}, whether it is possible to obtain a…
Parameterized Algorithms for Finding Square Roots
Manfred Cochefert, Jean-François Couturier, Petr A. Golovach +2
We show that the following two problems are fixed-parameter tractable with parameter k: testing whether a connected n-vertex graph with m edges has a square root with at most n-1+k…
Editing to a Connected Graph of Given Degrees
Petr A. Golovach
The aim of edge editing or modification problems is to change a given graph by adding and deleting of a small number of edges in order to satisfy a certain property. We consider th…
Long Circuits and Large Euler Subgraphs
Fedor V. Fomin, Petr A. Golovach
An undirected graph is Eulerian if it is connected and all its vertices are of even degree. Similarly, a directed graph is Eulerian, if for each vertex its in-degree is equal to it…
On the parameterized complexity of cutting a few vertices from a graph
Fedor V. Fomin, Petr A. Golovach, Janne H. Korhonen
We study the parameterized complexity of separating a small set of vertices from a graph by a small vertex-separator. That is, given a graph and integers , , the task is…
Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs
Rajesh Chitnis, Fedor V. Fomin, Petr A. Golovach
Bhawalkar, Kleinberg, Lewi, Roughgarden, and Sharma [ICALP 2012] introduced the Anchored k-Core problem, where the task is for a given graph G and integers b, k, and p to find an i…