Orienting graphs to optimize reachability

DOI10.1016/S0020-0190(97)00129-4zbMath1337.68130OpenAlexW1981849312MaRDI QIDQ290248

Neal E. Young, S. Louis Hakimi, Edward F. Schmeichel

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

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) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (11)

Approximation algorithms for orienting mixed graphs ⋮ On orientations maximizing total arc-connectivity ⋮ Wheel-Free Deletion Is W[2-Hard] ⋮ Route-enabling graph orientation problems ⋮ Approximation Algorithms for Orienting Mixed Graphs ⋮ Minimal comparability completions of arbitrary graphs ⋮ Competition-reachability of a graph ⋮ Complexity classification of some edge modification problems ⋮ NP-completeness results for edge modification problems ⋮ Unnamed Item ⋮ Improved approximation for orienting mixed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Approximability of maximum splitting of k-sets and some other Apx-complete problems
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Graph Sandwich Problems
• Permutation Graphs and Transitive Graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Comparability graph augmentation for some multiprocessor scheduling problems

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