Improved approximation for orienting mixed graphs

DOI10.1007/S00453-014-9932-2zbMath1336.05132OpenAlexW2570261317MaRDI QIDQ261342

Iftah Gamzu, Moti Medina

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

zbMATH Keywords

approximation algorithmsmixed graphsgraph orientation

Mathematics Subject Classification ID

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