Orienting graphs to optimize reachability

DOI10.1016/S0020-0190(97)00129-4MaRDI QIDQ290248zbMATH OpenOpenAlexFDO

Authors S. Louis Hakimi, E. Schmeichel, Neal E. Young

Publication date 1 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(97)00129-4

zbMATH Keywords

computational complexitygraph algorithmsorientation

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Recommendations

• On orientations and shortest paths
• Optimal Orientation On-Line
• A note on orientations of mixed graphs
• Path-driven orientation of mixed graphs
• Strongly connected orientations of mixed multigraphs

Cites work

• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Approximability of maximum splitting of k-sets and some other Apx-complete problems
• Comparability graph augmentation for some multiprocessor scheduling problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Graph Sandwich Problems
• Graph theory
• Optimization, approximation, and complexity classes
• Permutation Graphs and Transitive Graphs

Cited in

(17)

• Improved approximation for orienting mixed graphs
• Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees
• Approximation algorithms for orienting mixed graphs
• scientific article; zbMATH DE number 2230201 (Why is no real title available?)
• Approximation algorithms for orienting mixed graphs
• NP-completeness results for edge modification problems
• Connected reorientations of mixed multigraphs
• On orientations maximizing total arc-connectivity
• On orientations and shortest paths
• Competition-reachability of a graph
• Complexity classification of some edge modification problems
• Minimal comparability completions of arbitrary graphs
• Wheel-Free Deletion Is W[2]-Hard
• Route-enabling graph orientation problems
• Complexity of (arc)-connectivity problems involving arc-reversals or deorientations
• O'Reach: Even Faster Reachability in Large Graphs
• Strongly connected orientations of mixed multigraphs

This page was built for publication: Orienting graphs to optimize reachability

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