Length-bounded disjoint paths in planar graphs

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

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    16 Citaten (Scopus)

    Samenvatting

    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.
    Originele taal-2Engels
    Pagina's (van-tot)251-261
    TijdschriftDiscrete Applied Mathematics
    Volume120
    Nummer van het tijdschrift1-3
    DOI's
    StatusGepubliceerd - 2002

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Length-bounded disjoint paths in planar graphs'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit