Algorithms for Planar Graphs (Fall 2015)

Shay Mozes

Lecture 4 Video [previous] [next]

[+] Multiple Source Shortest Paths and Vector spaces

We finish the proof of correctness of the Multiple Source Shortest paths algorithm, and discuss various ways in which it can be used for reporting distances and shortest paths. We then begin to discuss vector spaces for graphs, which will be used to prove the cut-cycle duality and the existance of interdigitating trees.

Download Video: 720p

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