12 citations · 29 across the 11 of their papers we have counts for
3 papers · 1 filter
k-Gap Interval Graphs
Fedor V. Fomin, Serge Gaspers, Petr Golovach +5
We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real…
Towards optimal kernel for connected vertex cover in planar graphs
Lukasz Kowalik, Marcin Pilipczuk, Karol Suchan
We study the parameterized complexity of the connected version of the vertex cover problem, where the solution set has to induce a connected subgraph. Although this problem does no…
Complexity of Splits Reconstruction for Low-Degree Trees
Serge Gaspers, Mathieu Liedloff, Maya Stein +1
Given a vertex-weighted tree T, the split of an edge xy in T is min{s_x(xy), s_y(xy)} where s_u(uv) is the sum of all weights of vertices that are closer to u than to v in T. Given…