Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-21458-5_35 | CPM |
Keywords | Field | DocType |
mixed graph,approximation algorithm | Discrete mathematics,Strength of a graph,Comparability graph,Combinatorics,Line graph,Computer science,Directed graph,Null graph,Butterfly graph,Graph (abstract data type),Feedback arc set | Conference |
Volume | ISSN | Citations |
6661 | 0302-9743 | 5 |
PageRank | References | Authors |
0.53 | 17 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Elberfeld | 1 | 115 | 10.63 |
| Danny Segev | 2 | 233 | 17.05 |
| Colin R. Davidson | 3 | 5 | 0.53 |
| Dana Silverbush | 4 | 11 | 2.42 |
| Roded Sharan | 5 | 2792 | 186.61 |