Algorithms for Planar Graphs (Fall 2015)

Shay Mozes

Lecture 7 Video [previous] [next]

[+] Cycle Separators & Shortest Paths with Negative Lengths

We finish the proof of the cycle separator algorithm. We then start discussing a nearly-linear time algorithm for shortest paths in the presence of negative lengths. We develop the overall structure of the algorithm, but do not get a nearly linear algorithm yet. We identify tht the bottleneck is running the Bellman-Ford algorithm on the dense distance graph - the complete graph on vertices of a cycle separator, where the length of an edge in the DDG corresponds to the length of a shortest path between its endpoints in the underlying planar graph. 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/20 • [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.