6.889: Algorithms for Planar Graphs and Beyond (Fall 2011)

Erik Demaine, Shay Mozes, Christian Sommer, Siamak Tazari

[Home] [Problem Sets] [Project] [Lectures] [Problem Session Notes] [Klein's Book] [Accessibility]

Lecture 19 Video     [previous] [next]

[+] Flow in planar graphs II: maximum st-flow in directed planar graphs.

We present an O(n logn) time algorithm for maximum st-flow in directed planar graphs. The algorithm, due to Borradaile and Klein, is simple and elegant and resembles the MSSP algorithm of lecture 11. The analysis we present is due to Erickson.

Download Video: 360p, 720p

Lecture notes, page 1/12 • [previous page] • [next page] • [PDF]

Lecture notes, page 1/12 • [previous page] • [next page] • [PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.