On orientations and shortest paths

DOI10.1016/0024-3795(89)90481-3zbMATH Open0678.05027OpenAlexW2125585605MaRDI QIDQ1123899FDOQ1123899

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

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

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)

Cites Work

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

Cited In (14)

• 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
• Title not available (Why is that?)
• 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
• Orienteering with one endomorphism

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)