Approximation algorithms for orienting mixed graphs

DOI10.1016/J.TCS.2012.03.044zbMATH Open1296.05184OpenAlexW2172997278MaRDI QIDQ390889FDOQ390889

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

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

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)

Cites Work

• The Structure and Function of Complex Networks
• Reducibility among Combinatorial Problems
• A note on finding the bridges of a graph
• Parametrized complexity theory.
• Orienting graphs to optimize reachability
• On the approximability of reachability-preserving network orientations
• Exploiting Bounded Signal Flow for Graph Orientation Based on Cause–Effect Pairs
• Strongly connected orientations of mixed multigraphs
• Title not available (Why is that?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Improved Orientations of Physical Networks
• Approximation Algorithms for Directed Steiner Problems
• Some optimal inapproximability results
• A note on orientations of mixed graphs
• Improved algorithms for feedback vertex set problems
• Title not available (Why is that?)
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Title not available (Why is that?)
• Set connectivity problems in undirected graphs and the directed steiner network problem
• Robbins's Theorem for Mixed Multigraphs
• Title not available (Why is that?)

Cited In (6)

• Improved approximation for orienting mixed graphs
• Approximation algorithms for orienting mixed graphs
• Title not available (Why is that?)
• 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

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)