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…
Interconnection network with a shared whiteboard: Impact of (a)synchronicity on computing power
Florent Becker, Adrian Kosowski, Nicolas Nisse +2
In this work we study the computational power of graph-based models of distributed computing in which each node additionally has access to a global whiteboard. A node can read the…