Approximation algorithms for orienting mixed graphs

DOI10.1016/J.TCS.2012.03.044MaRDI QIDQ390889zbMATH OpenOpenAlexFDO

Authors Michael Elberfeld, Danny Segev, Colin R. Davidson, Dana Silverbush, Roded Sharan

Publication date 9 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.03.044

zbMATH Keywords

approximation algorithmmixed graphgraph orientationprotein-protein interaction network

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Systems biology, networks (92C42) Approximation algorithms (68W25)

Recommendations

• Approximation algorithms for orienting mixed graphs
• Improved approximation for orienting mixed graphs
• Improved approximation for orienting mixed graphs
• Improved Orientations of Physical Networks
• 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 2079393 (Why is no real title available?)
• scientific article; zbMATH DE number 1764950 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• A note on finding the bridges of a graph
• A note on orientations of mixed graphs
• Approximation Algorithms for Directed Steiner Problems
• Approximation algorithms for node-weighted buy-at-bulk network design
• Exploiting Bounded Signal Flow for Graph Orientation Based on Cause–Effect Pairs
• Improved Orientations of Physical Networks
• Improved algorithms for feedback vertex set problems
• On the approximability of reachability-preserving network orientations
• Orienting graphs to optimize reachability
• Parametrized complexity theory.
• Reducibility among combinatorial problems
• Robbins's Theorem for Mixed Multigraphs
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• Some optimal inapproximability results
• Strongly connected orientations of mixed multigraphs
• The Structure and Function of Complex Networks

Cited in

(9)

• Approximation algorithms and hardness results for shortest path based graph orientations
• Efficient algorithms to solve the link-orientation problem for multi-square, convex-bipartite, and convex-split networks
• On 2-strong connectivity orientations of mixed graphs and related problems
• Fast parallel strong orientation of mixed graphs and related augmentation problems
• On the approximability of reachability-preserving network orientations
• scientific article; zbMATH DE number 1985668 (Why is no real title available?)
• Approximation algorithms for orienting mixed graphs
• Improved approximation for orienting mixed graphs
• Improved approximation for orienting mixed graphs

This page was built for publication: Approximation algorithms for orienting mixed graphs

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