27
Mar
Friday, March 30th, 2007
3:30pm
WEH 7220
TITLE:
An O(n log n) algorithm for maximum st-flow in a directed planar graph
Glencora Borradaile
Brown University
ABSTRACT:
We give the first correct O(n log n) algorithm for finding a maximum single-source, single-sink maximum st-flow in a directed planar graph. After a preprocessing step that consists of finding single-source shortest path distances in the dual, the algorithms consists of repeatedly saturating the leftmost residual s-to-t path. While the algorithm is very simple, the analysis is more complicated.
I also will overview other planar graph algorithms that we are working on.
