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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Systems biology, networks (92C42)

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)

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