Seminario Interdipartimentale di Algoritmica
 
 

DIS - Department of Computer and System Sciences
Room C3, second floor

Abstract:

The goal of cache-oblivious algorithms is to efficiently use the whole memory hierarchies of modern computers. They are designed to be local, in the sense that, on a theoretical model with two memory levels managed by an optimal paging strategy (the ideal-cache model), they bound the number of memory transfers between levels. Bounds obtained on the ideal-cache model also hold, asymptotically, for any pair of adjacent levels of a real hierarchy.

After an introduction to cache-oblivious algorithms, I will 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)}.

Joint work with Peter Lichodzijewski and Norbert Zeh.