CENTER
Carnegie
Mellon School
of Computer Science|
Abstracts
|
The Joint ALADDIN/Theory/Operations Research Seminar |
|||||||||||||||||||||||||||||
|
Title TBA Glencora Borradaile
Abstract 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.
|
|||||||||||||||||||||||||||||
 |
This material is based upon work
supported by National Science Foundation under Grant No. 0122581.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation |
Aladdin
