OREGON STATE UNIVERSITY

You are here

An O(n log n) Algorithm for Maximum St-Flow in a Directed Planar Graph

TitleAn O(n log n) Algorithm for Maximum St-Flow in a Directed Planar Graph
Publication TypeJournal Article
Year of Publication2009
AuthorsBorradaile, G., and P. N. Klein
JournalJournal of the ACM
Volume56
Issue2
Pagination1 - 30
Date Published04/2009
ISSN00045411
Abstract

We give the first correct O(n log n) algorithm for finding a maximum st-flow in a directed planar graph. After a preprocessing step that consists in finding single-source shortest-path distances in the dual, the algorithm consists of repeatedly saturating the leftmost residual s-to-t path.

DOI10.1145/1502793.1502798
Short TitleJ. ACMJACM