Algorithms for Planar Graphs (Fall 2015)

Shay Mozes

Lecture 8 Video [previous] [next]

[+] Shortest paths with negative lengths

We show that implementing an iteration of Bellman-Ford can be cast into the problem of finding all column minima in the weighted incidence matrix of the DDG. We then introduce the Monge property, and show that we can find all column minima of a Monge matrix in time that is nearly linear in the number of rows. Finally we show that the weighted incidence matrix of the DDG can be decomposed into a small number of Monge matrices.

Download Video: 720p

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 me.