The Directed Disjoint Shortest Paths Problem

DOI10.4230/LIPICS.ESA.2017.13zbMATH Open1445.68149OpenAlexW2758462134MaRDI QIDQ5111698FDOQ5111698

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/

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

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)

Cites Work

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

Cited In (17)

• Theory and Applications of Models of Computation
• The undirected two disjoint shortest paths problem
• Title not available (Why is that?)
• The next‐to‐shortest path problem on directed graphs with positive edge weights
• Finding k Disjoint Paths in a Directed Planar Graph
• Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths
• Parameterizing path partitions
• Path partitions of phylogenetic networks
• Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
• The 2-disjoint path problem for circulant digraphs
• Efficient Algorithms for k-Disjoint Paths Problems on DAGs
• On the directed hop-constrained shortest path problem
• The directed 2-linkage problem with length constraints
• The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
• The Maximum Disjoint Routing Problem
• Title not available (Why is that?)
• Title not available (Why is that?)

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)