SPEAKER: Norbert Zeh

TITLE:  I/O-efficient and cache-oblivious shortest paths

ABSTRACT:  This talk covers the state of the art of undirected single-
source shortest path (SSSP) algorithms for memory hierarchies.  I  will
start by discussing two papers by Kumar/Schwabe and Mehlhorn/ Meyer,
respectively.  The Kumar/Schwabe algorithm isn't very  efficient,
but (a) forms the basis for all improved SSSP algorithms  in the
I/O-model and (b) highlights the central challenge to be  addressed.
The Mehlhorn/Meyer algorithm introduces, in the context  of breadth-first
search, the central clustering idea used in current  SSSP algorithms.
After this introduction, I will discuss a  progression of three papers
on I/O-efficient SSSP for graphs with  bounded real edge lengths,
I/O-efficient SSSP for graphs with  arbitrary real edge lengths, and
cache-oblivious SSSP for graphs with  bounded real edge lengths.