25 citations · 78 across the 26 of their papers we have counts for
Showing 2013 · cs.DSShow all
3 papers · 2 filters
cs.DS2013
Boundary-to-boundary flows in planar graphs
Glencora Borradaile, Anna Harutyunyan
We give an iterative algorithm for finding the maximum flow between a set of sources and sinks that lie on the boundary of a planar graph. Our algorithm uses only O(n) queries to s…
cs.DS2013
Maximum st-flow in directed planar graphs via shortest paths
Glencora Borradaile, Anna Harutyunyan
Minimum cuts have been closely related to shortest paths in planar graphs via planar duality - so long as the graphs are undirected. Even maximum flows are closely related to short…
cs.DS2013
The two-edge connectivity survivable-network design problem in planar graphs
Glencora Borradaile, Philip Klein
Consider the following problem: given a graph with edge costs and a subset Q of vertices, find a minimum-cost subgraph in which there are two edge-disjoint paths connecting every p…