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

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

We present an O(n log3n) time algorithm for maximum flow with multiple sources and sinks in directed planar graphs. The reduction from multiple sources and sinks to single sources and sinks violates planarity. The algorithm is radically different from the algorithm for maximum st-flows of lecture 19, and uses almost all the technique for exact algorithms in planar graphs that we covered in class so far.

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.