Network orientation via shortest paths
D Silverbush, R Sharan - Bioinformatics, 2014 - academic.oup.com
The graph orientation problem calls for orienting the edges of a graph so as to maximize the
number of pre-specified source–target vertex pairs that admit a directed path from the source …
number of pre-specified source–target vertex pairs that admit a directed path from the source …
The approximability of shortest path-based graph orientations of protein–protein interaction networks
D Blokh, D Segev, R Sharan - Journal of Computational Biology, 2013 - liebertpub.com
The graph orientation problem calls for orienting the edges of an undirected graph so as to
maximize the number of prespecified source-target vertex pairs that admit a directed path …
maximize the number of prespecified source-target vertex pairs that admit a directed path …
Improved orientations of physical networks
I Gamzu, D Segev, R Sharan - … , WABI 2010, Liverpool, UK, September 6-8 …, 2010 - Springer
The orientation of physical networks is a prime task in deciphering the signaling-regulatory
circuitry of the cell. One manifestation of this computational task is as a maximum graph …
circuitry of the cell. One manifestation of this computational task is as a maximum graph …
An algorithm for orienting graphs based on cause-effect pairs and its applications to orienting protein networks
We consider a graph orientation problem arising in the study of biological networks. Given
an undirected graph and a list of ordered source-target pairs, the goal is to orient the graph …
an undirected graph and a list of ordered source-target pairs, the goal is to orient the graph …
Approximation algorithms for orienting mixed graphs
M Elberfeld, D Segev, CR Davidson… - Theoretical Computer …, 2013 - Elsevier
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 …
study of signaling-regulatory pathways in protein networks. Given a graph and a list of …
Optimally orienting physical networks
D Silverbush, M Elberfeld, R Sharan - Journal of Computational …, 2011 - liebertpub.com
In a network orientation problem, one is given a mixed graph, consisting of directed and
undirected edges, and a set of source-target vertex pairs. The goal is to orient the undirected …
undirected edges, and a set of source-target vertex pairs. The goal is to orient the undirected …
On the approximability of reachability-preserving network orientations
M Elberfeld, V Bafna, I Gamzu, A Medvedovsky… - Internet …, 2011 - Taylor & Francis
We introduce a graph-orientation problem arising in the study of biological networks. Given
an undirected graph and a list of ordered source–target vertex pairs, the goal is to orient the …
an undirected graph and a list of ordered source–target vertex pairs, the goal is to orient the …
Improved approximation for orienting mixed graphs
I Gamzu, M Medina - International Colloquium on Structural Information …, 2012 - Springer
An instance of the maximum mixed graph orientation problem consists of a mixed graph and
a collection of source-target vertex pairs. The objective is to orient the undirected edges of …
a collection of source-target vertex pairs. The objective is to orient the undirected edges of …
Exploiting bounded signal flow for graph orientation based on cause–effect pairs
Background We consider the following problem: Given an undirected network and a set of
sender–receiver pairs, direct all edges such that the maximum number of" signal flows" …
sender–receiver pairs, direct all edges such that the maximum number of" signal flows" …
Pairwise global alignment of protein interaction networks by matching neighborhood topology
We describe an algorithm, IsoRank, for global alignment of two protein-protein interaction
(PPI) networks. IsoRank aims to maximize the overall match between the two networks; in …
(PPI) networks. IsoRank aims to maximize the overall match between the two networks; in …