21 citations · 83 across the 14 of their papers we have counts for
Showing 2013Show all
3 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.DS2013
Faster exponential-time algorithms in graphs of bounded average degree
Marek Cygan, Marcin Pilipczuk
We first show that the Traveling Salesman Problem in an n-vertex graph with average degree bounded by d can be solved in O*(2^{(1-\eps_d)n}) time and exponential space for a consta…
cs.DS2013★ 21 cited
On Pairwise Spanners
Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha
Given an undirected -node unweighted graph , a spanner with stretch function is a subgraph such that, if two nodes are at distance in $…