On orientations and shortest paths

DOI10.1016/0024-3795(89)90481-3MaRDI QIDQ1123899zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Route-enabling graph orientation problems
• Route-enabling graph orientation problems
• Orientations with single source and sink
• Orienting graphs to optimize reachability
• The complexity of two graph orientation problems

Cites work

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

Cited in

(14)

• Orienteering with one endomorphism
• Min-sum 2-paths problems
• Orienting graphs to optimize reachability
• The complexity of two graph orientation problems
• Path-driven orientation of mixed graphs
• The disjoint shortest paths problem
• Orientation distance graphs
• Series-parallel orientations preserving the cycle-radius
• A note on orientations of mixed graphs
• scientific article; zbMATH DE number 1305420 (Why is no real title available?)
• The edge-orientation problem and some of its variants on weighted graphs
• Directing Road Networks by Listing Strong Orientations
• Orientations with single source and sink
• A tight lower bound for planar Steiner orientation

This page was built for publication: On orientations and shortest paths

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