The Directed Disjoint Shortest Paths Problem

DOI10.4230/LIPICS.ESA.2017.13MaRDI QIDQ5111698zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• The disjoint shortest paths problem
• The undirected two disjoint shortest paths problem
• Disjoint shortest paths in graphs
• Shortest edge-disjoint paths in graphs
• On the directed hop-constrained shortest path problem
• Shortest two disjoint paths in polynomial time
• Shortest two disjoint paths in polynomial time
• The Induced Disjoint Paths Problem
• The Maximum Disjoint Routing Problem

Cites work

• scientific article; zbMATH DE number 16300 (Why is no real title available?)
• scientific article; zbMATH DE number 6146454 (Why is no real title available?)
• 2-linked graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• Disjoint paths in graphs
• Distributed algorithms for computing shortest pairs of disjoint paths
• Finding k Disjoint Paths in a Directed Planar Graph
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Graph minors. XIII: The disjoint paths problem
• Graph-Theoretic Concepts in Computer Science
• On shortest disjoint paths in planar graphs
• On the Computational Complexity of Combinatorial Problems
• Shortest \((A+B)\)-path packing via hafnian
• Shortest two disjoint paths in polynomial time
• The directed subgraph homeomorphism problem
• The disjoint paths problem in quadratic time
• The disjoint shortest paths problem
• Towards single face shortest vertex-disjoint paths in undirected planar graphs

Cited in

(22)

• The Maximum Disjoint Routing Problem
• The directed 2-linkage problem with length constraints
• Path partitions of phylogenetic networks
• Finding k Disjoint Paths in a Directed Planar Graph
• Efficient Algorithms for k-Disjoint Paths Problems on DAGs
• The next‐to‐shortest path problem on directed graphs with positive edge weights
• On the directed hop-constrained shortest path problem
• Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths
• scientific article; zbMATH DE number 1409242 (Why is no real title available?)
• A relaxation of the directed disjoint paths problem: a global congestion metric helps
• scientific article; zbMATH DE number 3922000 (Why is no real title available?)
• Theory and Applications of Models of Computation
• Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
• Shortest two disjoint paths in polynomial time
• The 2-disjoint path problem for circulant digraphs
• Parameterizing path partitions
• The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
• Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths
• Two disjoint shortest paths problem with non-negative edge length
• scientific article; zbMATH DE number 7765417 (Why is no real title available?)
• The undirected two disjoint shortest paths problem
• Exact algorithms for finding partial edge-disjoint paths

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111698)