Jeff Erickson talk at Caltech, 01/09, 11am
David Kempe
while this talk is *not* at USC, I figured that people subscribing to
this list might still be interested in attending it. Jeff Erickson
from UIUC will be giving a talk at Caltech this Friday (January 9).
The full information:
Title: Homology Flows, Cohomology Cuts
Speaker: Jeff Erickson, UIUC
When: 11:00am-Noon, Friday, January 9, 2009
Where: 100 Powell-Booth, Caltech
Map and directions: http://www.caltech.edu/map/
Abstract:
I will describe the first algorithms to compute maximum flows and
minimum cuts in surface-embedded graphs in near-linear time. Given a
undirected edge-weighted graph embedded on a fixed orientable surface,
and two vertices s and t, our algorithms compute the minimum (s,t)-cut
in O(n log n) time, and the maximum (s,t)-flow in O(n polylog n) time.
Our results generalize O(n log n)-time algorithms for planar graphs
have been known for more than 20 years. Even for graphs embedded on
the torus, the best previous algorithms have no better performance
than for general sparse graphs. The key insight in our flow algorithm
is to optimize the homology class of the flow, rather than directly
optimizing the flow itself. Our results exploit intimate connections
between combinatorial duality of graph embeddings, linear programming
duality between flows and cuts, and Poincaré-Alexander-Lefschetz
duality between (relative) homology and cohomology.
The talk will be self-contained. In particular, I will assume no
previous exposure to maximum flows, minimum cuts, or homology.
This is joint work with Erin Chambers and Amir Nayyeri.