Two disjoint shortest paths problem with non-negative edge length

DOI10.1016/J.ORL.2018.11.012MaRDI QIDQ2294269zbMATH OpenOpenAlexWikidataFDO

Authors Yusuke Kobayashi, Ryo Sako

Publication date 10 February 2020

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2433/244836

zbMATH Keywords

disjoint pathspolynomial-time algorithmshortest path

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Recommendations

• The undirected two disjoint shortest paths problem
• The Directed Disjoint Shortest Paths Problem
• The disjoint shortest paths problem
• On shortest disjoint paths in planar graphs
• STACS 2004

Cites work

• 2-linked graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
• Disjoint paths in graphs
• Graph minors. XIII: The disjoint paths problem
• On the Computational Complexity of Combinatorial Problems
• The directed subgraph homeomorphism problem
• The disjoint shortest paths problem

Cited in

(13)

• The disjoint shortest paths problem
• Exact algorithms for finding partial edge-disjoint paths
• The undirected two disjoint shortest paths problem
• The directed 2-linkage problem with length constraints
• Two edge-disjoint paths with length constraints
• The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
• Finding two edge-disjoint paths with length constraints
• The 2-disjoint path problem for circulant digraphs
• scientific article; zbMATH DE number 7765417 (Why is no real title available?)
• Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths
• Lower bounds for approximate (\& exact) k-disjoint-shortest-paths
• Lower bounds for approximate (\& exact) \(k\)-\textsc{Disjoint-Shortest-Paths}
• Using a geometric Lens to find k disjoint shortest paths

This page was built for publication: Two disjoint shortest paths problem with non-negative edge length

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