Orienting graphs to optimize reachability
DOI10.1016/S0020-0190(97)00129-4zbMATH Open1337.68130OpenAlexW1981849312MaRDI QIDQ290248FDOQ290248
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
Recommendations
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)
Cites Work
- Graph theory
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- Graph Sandwich Problems
- Title not available (Why is that?)
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- An Algorithmic Approach to Network Location Problems. II: Thep-Medians
- A Characterization of Comparability Graphs and of Interval Graphs
- Approximability of maximum splitting of k-sets and some other Apx-complete problems
- Permutation Graphs and Transitive Graphs
- A Theorem on Graphs, with an Application to a Problem of Traffic Control
- Comparability graph augmentation for some multiprocessor scheduling problems
Cited In (16)
- Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees
- Title not available (Why is that?)
- Improved approximation for orienting mixed graphs
- Approximation algorithms for orienting mixed graphs
- 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
- 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)
