On orientations and shortest paths

DOI10.1016/0024-3795(89)90481-3zbMath0678.05027OpenAlexW2125585605MaRDI QIDQ1123899

Refael Hassin, Nimrod Megiddo

Publication date: 1989

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0024-3795(89)90481-3

zbMATH Keywords

digraphNP-completeideal orientationpolylogarithmic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Related Items

The disjoint shortest paths problem ⋮ The complexity of two graph orientation problems ⋮ Series-parallel orientations preserving the cycle-radius ⋮ Path-driven orientation of mixed graphs ⋮ A tight lower bound for planar Steiner orientation ⋮ A note on orientations of mixed graphs ⋮ The edge-orientation problem and some of its variants on weighted graphs ⋮ Directing Road Networks by Listing Strong Orientations ⋮ Min-sum 2-paths problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The directed subgraph homeomorphism problem
• On the orientation of graphs
• Disjoint paths in graphs
• Distances in orientations of graphs
• A note on finding the bridges of a graph
• On the degrees of the vertices of a directed graph
• Covering directed and odd cuts
• A linear programming approach to the optimum network orientation problem
• Fast parallel strong orientation of mixed graphs and related augmentation problems
• Robbins's Theorem for Mixed Multigraphs
• A Polynomial Solution to the Undirected Two Paths Problem
• On the Complexity of Timetable and Multicommodity Flow Problems
• An Algorithm for Submodular Functions on Graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Depth-First Search and Linear Graph Algorithms
• A Characterization of Comparability Graphs and of Interval Graphs
• A Theorem on Graphs, with an Application to a Problem of Traffic Control