Length-bounded disjoint paths in planar graphs |
| |
Authors: | H van der Holst J C de Pina |
| |
Institution: | a Fachbereich Mathematik und Informatik, Freie Universität Berlin, Arnimallee 2-6, D-14195, Berlin, Germany b Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-900, São Paulo, Brazil |
| |
Abstract: | The following problem is considered: given: an undirected planar graph G=(V,E) embedded in
, distinct pairs of vertices {r1,s1},…,{rk,sk} of G adjacent to the unbounded face, positive integers b1,…,bk and a function
; find: pairwise vertex-disjoint paths P1,…,Pk such that for each i=1,…,k, Pi is a ri?si-path and the sum of the l-length of all edges in Pi is at most bi. It is shown that the problem is NP-hard in the strong sense. A pseudo-polynomial-time algorithm is given for the case of k=2. |
| |
Keywords: | Planar graphs Disjoint paths Complexity Dynamic programming |
本文献已被 ScienceDirect 等数据库收录! |
|