The Directed Disjoint Shortest Paths Problem

DOI10.4230/LIPIcs.ESA.2017.13zbMath1445.68149OpenAlexW2758462134MaRDI QIDQ5111698

Kristóf Bérczi, Yusuke Kobayashi

Publication date: 27 May 2020

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7824/pdf/LIPIcs-ESA-2017-13.pdf/

zbMATH Keywords

shortest pathpolynomial-time algorithmdisjoint paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Related Items (6)

Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths ⋮ The complexity of routing problems in forbidden-transition graphs and edge-colored graphs ⋮ Unnamed Item ⋮ The undirected two disjoint shortest paths problem ⋮ The directed 2-linkage problem with length constraints

Cites Work

• Unnamed Item
• Unnamed Item
• The disjoint paths problem in quadratic time
• On shortest disjoint paths in planar graphs
• Shortest \((A+B)\)-path packing via hafnian
• The directed subgraph homeomorphism problem
• Disjoint paths in graphs
• 2-linked graphs
• The disjoint shortest paths problem
• Graph minors. XIII: The disjoint paths problem
• Towards Single Face Shortest Vertex-Disjoint Paths in Undirected Planar Graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• On the Computational Complexity of Combinatorial Problems
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Distributed algorithms for computing shortest pairs of disjoint paths
• Finding k Disjoint Paths in a Directed Planar Graph
• Shortest Two Disjoint Paths in Polynomial Time
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: The Directed Disjoint Shortest Paths Problem