Approximation Algorithms for Orienting Mixed Graphs

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


Graph orientation is a fundamental problem in graph theory that has recently arisen in the study of signaling-regulatory pathways in protein networks. Given a graph and a list of ordered source-target vertex pairs, it calls for assigning directions to the edges of the graph so as to maximize the number of pairs that admit a directed source-to-target path. When the input graph is undirected, a sub-logarithmic approximation is known for the problem. However, the approximability of the biologically-relevant variant, in which the input graph has both directed and undirected edges, was left open. Here we give the first approximation algorithm to this problem. Our algorithm provides a sub-linear guarantee in the general case, and logarithmic guarantees for structured instances.
TitelCombinatorial Pattern Matching
Redakteure/-innenRaffaele Giancarlo, Giovanni Manzini
ErscheinungsortBerlin, Heidelberg
Herausgeber (Verlag)Springer Berlin Heidelberg
ISBN (Print)978-3-642-21457-8
ISBN (elektronisch)978-3-642-21458-5
PublikationsstatusVeröffentlicht - 06.2011
Veranstaltung22nd Annual Symposium, CPM 2011 - Palermo, Italien
Dauer: 27.06.201129.06.2011


Untersuchen Sie die Forschungsthemen von „Approximation Algorithms for Orienting Mixed Graphs“. Zusammen bilden sie einen einzigartigen Fingerprint.