Meeting Details

Schedule: 28/04/2011 12:00

Title: Approximation Algorithms for Graph Orientation Problems

Presenter: Danny Segev

Graph orientation is a fundamental problem in graph theory that has recently arisen in the study of signaling-regulatory pathways in protein networks. Somewhat informally, given a graph and a list of ordered source-target vertex pairs, we wish to assign edge directions so as to maximize the number of pairs that admit a directed source-to- target path.
In this talk, I plan on presenting (the currently best known) approximation algorithms for both undirected and mixed graphs. These attain, in particular, sub-logarithmic and sub-linear performance guarantees for the undirected and mixed cases, respectively.
Based on joint papers with: Vineet Bafna, Colin Davidson, Michael Elberfeld, Iftah Gamzu, Alexander Medvedovsky, Roded Sharan, Dana Silverbush, and Uri Zwick.