We study the ALT algorithm [19] for the point-to-point shortest path problem in the context of
road networks. We suggest improvements to the algorithm itself and to its preprocessing …

This paper presents two dynamic search trees attaining near-optimal performance on any
hierarchical memory. The data structures are independent of the parameters of the memory …

This work treats the problem of designing data-oblivious algorithms for classical and widely
used graph problems. A data-oblivious algorithm is defined as having the same sequence of …

We present the software library Stxxl that is an implementation of the C++ standard template
library (STL) for processing huge data sets that can fit only on hard disks. It supports parallel …

A major challenge in processing real-world graphs stems from poor locality of memory
accesses and vertex reordering algorithms (RAs) have been proposed to improve locality by …

This paper is an algorithmic engineering study of cache-oblivious sorting. We investigate by
empirical methods a number of implementation issues and parameter choices for the cache …

The systematic development of efficient algorithms has become a key technology for all
kinds of ambitious and innovative computer applications. With major parts of algorithmic …

We study the impact of using different priority queues in the performance of Dijkstra's SSSP
algorithm. We consider only general priority queues that can handle any type of keys …

Back in 1964 Williams introduced the binary heap as a basic priority queue data structure
supporting the operations Insert and ExtractMin in logarithmic time. Since then numerous …

Abstract Breadth First Search (BFS) traversal is an archetype for many important graph
problems. However, computing a BFS level decomposition for massive graphs was …