TY - GEN
T1 - Planar disjoint-paths completion
AU - Adler, Isolde
AU - Kolliopoulos, Stavros G.
AU - Thilikos, Dimitrios M.
PY - 2012
Y1 - 2012
N2 - We introduce Planar Disjoint Paths Completion, a completion counterpart of the Disjoint Paths problem, and study its parameterized complexity. The problem can be stated as follows: given a plane graph G, k pairs of terminals, and a face F of G, find a minimum-size set of edges, if one exists, to be added inside F so that the embedding remains planar and the pairs become connected by k disjoint paths in the augmented network. Our results are twofold: first, we give an explicit bound on the number of necessary additional edges if a solution exists. This bound is a function of k, independent of the size of G. Second, we show that the problem is fixed-parameter tractable, in particular, it can be solved in time f(k)•n 2.
AB - We introduce Planar Disjoint Paths Completion, a completion counterpart of the Disjoint Paths problem, and study its parameterized complexity. The problem can be stated as follows: given a plane graph G, k pairs of terminals, and a face F of G, find a minimum-size set of edges, if one exists, to be added inside F so that the embedding remains planar and the pairs become connected by k disjoint paths in the augmented network. Our results are twofold: first, we give an explicit bound on the number of necessary additional edges if a solution exists. This bound is a function of k, independent of the size of G. Second, we show that the problem is fixed-parameter tractable, in particular, it can be solved in time f(k)•n 2.
KW - Completion Problems
KW - Disjoint Paths
KW - Planar Graphs
UR - http://www.scopus.com/inward/record.url?scp=84858376541&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84858376541&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-28050-4_7
DO - 10.1007/978-3-642-28050-4_7
M3 - Conference contribution
AN - SCOPUS:84858376541
SN - 9783642280498
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 80
EP - 93
BT - Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers
T2 - 6th International Symposium on Parameterized and Exact Computation, IPEC 2011
Y2 - 6 September 2011 through 8 September 2011
ER -