Algorithms for Planar Graphs (Fall 2013)

Shay Mozes

Lecture 8 Video [previous] [next]

[+] Exact Distance Oracles and Branchwidth

We conclude the discussion of FR-Dijkstra and go into a relatively short discussion of exact distance oracles for planar graphs. We apply MSSP and FR-Dikstra to obtain a data stucture with nearly linear space and preprocessing time, that can answer distance queries in roughly √n time.
We then move on to a new topic - approximation schemes, and discuss carving and branch decompositions.

Download Video: 360p, 720p

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