Length-bounded disjoint paths in planar graphs

H. Holst, van der; J.C. Pina, de

doi:10.1016/S0166-218X(01)00294-3

Length-bounded disjoint paths in planar graphs

H. Holst, van der, J.C. Pina, de

Research output: Contribution to journal › Article › Academic › peer-review

16 Citations (Scopus)

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.

Original language	English
Pages (from-to)	251-261
Journal	Discrete Applied Mathematics
Volume	120
Issue number	1-3
DOIs	https://doi.org/10.1016/S0166-218X(01)00294-3
Publication status	Published - 2002

Access to Document

10.1016/S0166-218X(01)00294-3

Cite this

@article{545837b6022a4410840566084d7ce3d6,

title = "Length-bounded disjoint paths in planar graphs",

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.",

author = "\{Holst, van der\}, H. and \{Pina, de\}, J.C.",

year = "2002",

doi = "10.1016/S0166-218X(01)00294-3",

language = "English",

volume = "120",

pages = "251--261",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Length-bounded disjoint paths in planar graphs

AU - Holst, van der, H.

AU - Pina, de, J.C.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

U2 - 10.1016/S0166-218X(01)00294-3

DO - 10.1016/S0166-218X(01)00294-3

M3 - Article

SN - 0166-218X

VL - 120

SP - 251

EP - 261

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

Length-bounded disjoint paths in planar graphs

Abstract

Access to Document

Fingerprint

Cite this