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

[+] Shortest paths with negative lengths in planar graphs.

We conclude our discussion of shortest paths by describing a near-linear time algorithm for shortest paths in directed planar graphs with negative arc lengths (but no negative-length cycles). We define the Monge property for matrices and introduce an algorithm nicknamed SMAWK (due to Aggarwal, Klawe, Moran, Shor and Wilber) for efficient search in Monge matrices. The notes also sketch a generalization of the shortest paths algorithm to graphs with bounded genus.

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.