Portal de Periódicos da CAPES

Artigo Produção Nacional Revisado por pares

BIBTEX RIS

Length-bounded disjoint paths in planar graphs

2002; Elsevier BV; Volume: 120; Issue: 1-3 Linguagem: Inglês

10.1016/s0166-218x(01)00294-3

1872-6771

Hein van der Holst, José Coelho de Pina,

Optimization and Search Problems

The following problem is considered: given: an undirected planar graph G=(V,E) embedded in R2, distinct pairs of vertices {r1,s1},…,{rk,sk} of G adjacent to the unbounded face, positive integers b1,…,bk and a function l:E→Z+; 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.