Approximation algorithms and hardness results for shortest path based graph orientations

DOI10.1007/978-3-642-31265-6_6MaRDI QIDQ2904480zbMATH OpenOpenAlexFDO

Authors Dima Blokh, Danny Segev, Roded Sharan

Publication date 14 August 2012

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31265-6_6

Mathematics Subject Classification ID

Applications of graph theory (05C90) Systems biology, networks (92C42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• On the approximability of reachability-preserving network orientations
• Approximation algorithms for orienting mixed graphs
• Approximation algorithms for orienting mixed graphs
• Improved Orientations of Physical Networks
• Route-enabling graph orientation problems

Cited in

(12)

• Minimum-cost strong network orientation problems: Classification, complexity, and algorithms
• Improved approximation for orienting mixed graphs
• Approximation algorithms for orienting mixed graphs
• On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
• Approximation algorithms for orienting mixed graphs
• The complexity of two graph orientation problems
• A note on the parameterized complexity of unordered maximum tree orientation
• Route-enabling graph orientation problems
• Efficient algorithms to solve the link-orientation problem for multi-square, convex-bipartite, and convex-split networks
• On the approximability of reachability-preserving network orientations
• Route-enabling graph orientation problems
• On finding orientations with the fewest number of vertices with small out-degree

This page was built for publication: Approximation algorithms and hardness results for shortest path based graph orientations

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