Name
Abstract | ||
|---|---|---|
Given a graph G and k pairs of vertices (s1, t1), ..., (sk, tk), the k-Vertex-Disjoint Paths problem asks for pair wise vertex-disjoint paths P1, ..., Pk such that Pi goes from si to ti. Schrijver [SICOMP'94] proved that the k-Vertex-Disjoint Paths problem on planar directed graphs can be solved in time nO(k). We give an algorithm with running time 22O(k2) * nO(1) for the problem, that is, we show the fixed-parameter tractability of the problem. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/FOCS.2013.29 | foundations of computer science |
Keywords | DocType | Volume |
pair wise vertex-disjoint path,k-vertex-disjoint paths problem,planar directed k-vertex-disjoint paths,k pair,fixed-parameter tractability,graph g,time no,fixed-parameter tractable,computational complexity,directed graphs | Conference | abs/1304.4207 |
ISSN | Citations | PageRank |
0272-5428 | 12 | 0.59 |
References | Authors | |
16 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marek Cygan | 1 | 556 | 40.52 |
| Dániel Marx | 2 | 1952 | 113.07 |
| Marcin Pilipczuk | 3 | 436 | 47.86 |
| michal pilipczuk | 4 | 403 | 51.93 |