121 citations · 375 across the 53 of their papers we have counts for
Showing cs.DMShow all
2 papers · 1 filter
cs.DM2013
The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable
Marek Cygan, Dániel Marx, Marcin Pilipczuk +1
Given a graph G and k pairs of vertices (s_1,t_1), ..., (s_k,t_k), the k-Vertex-Disjoint Paths problem asks for pairwise vertex-disjoint paths P_1, ..., P_k such that P_i goes from…
cs.DM2011
Parameterized Complexity of Firefighting Revisited
Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen
The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a fire…