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 21 Video     [previous] [next]

[+] Flow in planar graphs IV: maximum flow with multiple sources and sinks in directed planar graphs.

We continue the presentation of the O(n log3n) time algorithm for maximum flow with multiple sources and sinks in directed planar graphs. After a short recap of where we left off at the end of lecture 20, we finish the description of the procedure to eliminate residual paths between nodes with positive and negative excess on a cycle. Then we discuss some additional complication that arise in the recursive approach.

Download Video: 360p, 720p

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

Lecture notes, page 1/16 • [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.