SPP 1126 - Algorithm Engineering for Large Graphs

This is part of the DFG Schwerpunkt Nr. 1126, Algorithmik großer und komplexer Netzwerke.

Basic graph algorithms for depth first search, breadth first search, shortest paths, spanning trees or network flows are well established compenents of every algorithms course and many applications. Theory has produced advanced algorithms for these problems that should theoretically be superior to the simple text book methods. The starting point of this project is to explore the possibility to transform such advanced approaches in to practicable algorithms and implementations. We are particularly interested in algorithms that can exploit parallelism and memory hierarchies.

Specific Topics

Graph Traversal

• External-Memory Breadth-First Search with Sublinear I/O (ESA 2002).
• Buckets Strike Back: Improved Parallel Shortest-Paths (IPDPS 2002).
• Heuristics for Semi-External Depth First Search on Directed Graphs (SPAA 2002).
• Algorithms and experiments for the webgraph (ESA 2003).
• I/O-Efficient Undirected Shortest Paths (ESA 2003).
• External memory algorithms for diameter and all-pairs shortest-paths on sparse graphs (ICALP 2004).
• Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths (SWAT 2004).
• A computational study of external memory BFS algorithms (SODA 2006).
• Goal Directed Shortest Path Queries Using Precomputed Cluster Distances (WEA 2006).
• An O(n2.75) algorithm for online topological ordering (SWAT 2006).
• Engineering Highway Hierarchies (ESA 2006).
• I/O-Efficient Undirected Shortest Paths with Unbounded Weights (ESA 2006).