On the complexity of the edge-disjoint min-min problem in planar digraphs

DOI10.1016/j.tcs.2011.12.009zbMath1242.68114OpenAlexW2049003114MaRDI QIDQ428855

Longkun Guo, Hong Shen

Publication date: 25 June 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.009

zbMATH Keywords

NP-completeinapproximabilitydisjoint pathmin-min problemplanar digraph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Related Items

Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths, Improved approximation algorithms for computing \(k\) disjoint paths subject to two constraints

Cites Work

• The complexity of finding two disjoint paths with min-max objective function
• Finding disjoint paths with related path costs
• The directed subgraph homeomorphism problem
• Length-bounded disjoint paths in planar graphs
• On finding Min-Min disjoint paths
• Disjoint paths in graphs. (Reprint)
• A quick method for finding shortest pairs of disjoint paths
• A Polynomial Solution to the Undirected Two Paths Problem
• Finding disjoint paths with different path-costs: Complexity and algorithms
• Disjoint paths in a network
• Efficient Planarity Testing
• Finding k Disjoint Paths in a Directed Planar Graph