Improved approximation for orienting mixed graphs

DOI10.1007/S00453-014-9932-2MaRDI QIDQ261342zbMATH OpenOpenAlexFDO

Authors 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 algorithmsgraph orientationmixed graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Improved approximation for orienting mixed graphs
• Approximation algorithms for orienting mixed graphs
• Approximation algorithms for orienting mixed graphs
• Improved bounds for the oriented radius of mixed multigraphs
• Path-driven orientation of mixed graphs
• Fast parallel strong orientation of mixed graphs and related augmentation problems
• The complexity of 2-vertex-connected orientation in mixed graphs
• A note on orientations of mixed graphs
• Algorithms and Computation
• Approximation algorithms and hardness results for shortest path based graph orientations

Cites work

• scientific article; zbMATH DE number 3709597 (Why is no real title available?)
• scientific article; zbMATH DE number 1332672 (Why is no real title available?)
• scientific article; zbMATH DE number 2086914 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A note on orientations of mixed graphs
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• A sublogarithmic approximation for highway and tollbooth pricing
• Approximation algorithms and hardness results for shortest path based graph orientations
• Approximation algorithms for orienting mixed graphs
• Distributed Algorithms For Unidirectional Networks
• Exploiting Bounded Signal Flow for Graph Orientation Based on Cause–Effect Pairs
• Improved Orientations of Physical Networks
• Improved approximation for orienting mixed graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On the approximability of reachability-preserving network orientations
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Orienting graphs to optimize reachability
• Some optimal inapproximability results

Cited in

(8)

• Fast parallel strong orientation of mixed graphs and related augmentation problems
• Path-driven orientation of mixed graphs
• Algorithms and Computation
• Augmenting weighted graphs to establish directed point-to-point connectivity
• Approximation algorithms for orienting mixed graphs
• Improved approximation for orienting mixed graphs
• Approximation algorithms for orienting mixed graphs
• Improved approximation for orienting mixed graphs

This page was built for publication: Improved approximation for orienting mixed graphs

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