Orienting graphs to optimize reachability

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

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)

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

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)