Length-bounded disjoint paths in planar graphs

DOI10.1016/S0166-218X(01)00294-3zbMath1019.05039OpenAlexW2021673830MaRDI QIDQ1613380

Hein van der Holst, José C. de Pina

Publication date: 29 August 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00294-3

zbMATH Keywords

complexitydynamic programmingplanar graphsdisjoint paths

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39) Paths and cycles (05C38)

Related Items (7)

On finding Min-Min disjoint paths ⋮ On the complexity of the edge-disjoint min-min problem in planar digraphs ⋮ Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph ⋮ A note on approximating the min-max vertex disjoint paths on directed acyclic graphs ⋮ Hardness of Finding Two Edge-Disjoint Min-Min Paths in Digraphs ⋮ Maximum thick paths in static and dynamic environments ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of finding two disjoint paths with min-max objective function
• On the complexity of integer programming
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• The complexity of finding maximum disjoint paths with length constraints
• The complexity of theorem-proving procedures

This page was built for publication: Length-bounded disjoint paths in planar graphs