Approximation algorithms and hardness results for shortest path based graph orientations
DOI10.1007/978-3-642-31265-6_6zbMATH Open1358.68319OpenAlexW142788616MaRDI QIDQ2904480FDOQ2904480
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
Recommendations
Applications of graph theory (05C90) Systems biology, networks (92C42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cited In (12)
- Improved approximation for orienting mixed graphs
- Approximation algorithms 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
- 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
- Minimum-cost strong network orientation problems: Classification, complexity, and algorithms
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)
