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.

Here is an excerpt from the project proposal (in German) which contains some more information and pointers to relevant literature.

And here is talk on a similar topic presented at the Dagstuhl-Seminar on Algorithmic Aspects of Large and Complex Networks September 16-21, 2001.

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(n^2.75) algorithm for online topological ordering (SWAT 2006).
• Engineering Highway Hierarchies (ESA 2006).
• I/O-Efficient Undirected Shortest Paths with Unbounded Weights (ESA 2006).

Algorithms for Ad Hoc Radio Networks

• Energy Optimal Routing in Radio Networks (ICALP 2002).
• Approximating energy efficient paths in multi-hop wireless networks (ESA 2003).
• Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks (A_SWAN 2004).
• A simple improved distributed Algorithm for minimum CDS in Unit-Disk Graphs (WiMob 2005).

Problems related to Matching

• A simpler linear time 2/3-eps approximation for maximum weight matching (Information Processing Letters, 2004).
• Computing Approximate Matchings in Parallel, External, Distributed, and Streaming Models (2005, submitted).
• An Asymptotic Approximation Scheme for Multigraph Edge Coloring (SODA 2005).

Misc.

• Polynomial Time Algorithms For Network Information Flow (SPAA 2003). This is a result that came out of cooperation within the Schwerpunkt. The paper was presented on the Workshop on Flows in Networks in Bielefeld (slides).
• Space Efficient Hash Tables With Worst Case Constant Access Time (STACS 2003). This algorithm can be viewed a bipartite matching algorithm that needs linear average time.
• A Practical Minimum Spanning Tree Algorithm Using the Cycle Property

People

• Ulrich Meyer, Coordinator at MPII.
• Peter Sanders, UKA, Coordinator at UKA.

• Deepak Ajwani, MPII. PhD candidate. Design and Implementation of External Memory BFS Algorithms.
• Surender Baswana, MPII. Postdoc at MPII, works on spanners.
• Roman Dementiev, UKA. Has been employed on project funding. He works on a library for external memory algorithms and on external memory graph algorithms.
• Domagoj Matijevic, MPII. Currently employed by project money. He works on shortest paths with precomputations.
• Jens Maue, MPII. Implemented a shortest paths preprocessing heuristic in his Diploma thesis.
• Seth Pettie, MPII. Postdoc at MPII; recently worked on external graph algorithms for matchings.
• Dominik Schultes, UKA. External-memory MST and Highway Graphs.
• Karsten Sperling, UKA Sarted his master thesis on graph partitioning.
• David Steurer, Uni-SB. Works on multigraph edge coloring and graph partitioning.

Contact at MPII:

Dr. Ulrich Meyer
Max-Planck-Institut für Informatik
Stuhlsatzenhausweg 85
66123 Saarbrücken
Germany

Email: "u" + lastname @ mpi-sb.mpg.de
Phone: ++49 681-9325 125
Fax: ++49 681-9325 199
WWW: http://www.mpi-sb.mpg.de/~umeyer/

Contact at Karlsruhe university:

Prof. Dr. Peter Sanders
Universitaet Karlsruhe
Fakultaet fuer Informatik
Postfach 6980
76128 Karlsruhe
Germany

Email: lastname @ iru.uka.de
Phone: ++49 721 608 6580
Fax: ++49 721 608 3088
WWW: http://i10www.ira.uka.de/sanders/