Improved approximation for orienting mixed graphs
From MaRDI portal
Publication:261342
DOI10.1007/S00453-014-9932-2zbMath1336.05132OpenAlexW2570261317MaRDI QIDQ261342
Publication date: 23 March 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-014-9932-2
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)
Related Items (2)
Augmenting weighted graphs to establish directed point-to-point connectivity ⋮ Improved approximation for orienting mixed graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation for orienting mixed graphs
- Orienting graphs to optimize reachability
- Approximation algorithms for orienting mixed graphs
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- Approximation Algorithms and Hardness Results for Shortest Path Based Graph Orientations
- On the Approximability of Reachability-Preserving Network Orientations
- Exploiting Bounded Signal Flow for Graph Orientation Based on Cause–Effect Pairs
- A Sublogarithmic Approximation for Highway and Tollbooth Pricing
- Distributed Algorithms For Unidirectional Networks
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Improved Orientations of Physical Networks
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A note on orientations of mixed graphs
This page was built for publication: Improved approximation for orienting mixed graphs