25 citations · 78 across the 26 of their papers we have counts for
4 papers · 1 filter
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…
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…
A polynomial-time approximation scheme for Euclidean Steiner forest
Glencora Borradaile, Philip Klein, Claire Mathieu
We give a randomized O(n polylog n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed eps > 0 and given n terminals in the plane with…
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…