G. Borradaile

activity

20092021

most citedEgalitarian Graph Orientations

25 citations · 78 across the 26 of their papers we have counts for

collaborators

Showing 2010Show all

3 papers · 1 filter

cs.DM2010★ 1 cited

Multiple source, single sink maximum flow in a planar graph

Glencora Borradaile, Christian Wulff-Nilsen

We give an $O (n^{1.5} lo g n)$ time algorithm for finding the maximum flow in a directed planar graph with multiple sources and a single sink. The techniques generalize to a subquad…

cs.CG2010

Randomly removing g handles at once

Glencora Borradaile, James R. Lee, Anastasios Sidiropoulos

Indyk and Sidiropoulos (2007) proved that any orientable graph of genus $g$ can be probabilistically embedded into a graph of genus $g - 1$ with constant distortion. Viewing a graph…

cs.DM2010★ 9 cited

Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time

Glencora Borradaile, Piotr Sankowski, Christian Wulff-Nilsen

For an undirected $n$ -vertex planar graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$ , what is the weight of…