## January 7, Winter Quarter 2010: Theory Seminar

### 1:00pm in 4011 Bren Hall

#
Minimum Cuts and Homology Flows

## Erin Wolf Chambers, Saint Louis Univ.

Abstract:
We describe the first algorithms to compute maximum flows and minimum
cuts in surface-embedded graphs in near-linear time. Given an
undirected graph embedded on an orientable surface of genus g, with
two specified vertices s and t, our algorithm computes a minimum
(s,t)-cut in g^{O(g)} n log n time; if there is time, we will also
describe a different algorithm which computes a maximum $(s,t)$-flow
in in $O(g7 n \log^2n \log^2C)$ time for integer capacities that sum
to $C$, or in $(g \log n)^O(g) n$ time for real capacities. Except
for
the special case of planar graphs, the best previous time bounds for
finding min cuts or max flows in embedded graphs follow from
algorithms for general sparse graphs.

This is joint work with Jeff Erickson and Amir Nayyeri, which
appeared
in SOCG and STOC last year.