ICS Theory Group

CompSci 269S, Fall 2007: Theory Seminar

November 2, 2007, 1:00pm, in Bren Hall 1423

A Faster Cache-Oblivious Shortest-Path Algorithm for Undirected Graphs with Bounded Edge Lengths

presented by Kevin Wortman


We present a cache-oblivious algorithm for computing single-source shortest paths in undirected graphs with non-negative edge lengths. The algorithm incurs O(sqrt(nm log w)/B+(m/B) log n +MST (n, m)) memory transfers on a graph with n vertices, m edges, and real edge lengths between 1 and W; B denotes the cache block size, and MST(n, m) denotes the number of memory transfers required to compute a minimum spanning tree of a graph with n vertices and m edges. Our algorithm is the first cache-oblivious shortest-path algorithm incurring less than one memory transfer per vertex if the graph is sparse (m = O(n)) and W = 2^o(B).

This paper was authored by Luca Allulli, Peter Lichodzijewski, and Norbert Zeh, and appeared in SODA 2007.