## 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

Abstract:

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.