[Logo] HEIGHT=84 WIDTH=160 [Logo] HEIGHT=84 WIDTH=100

Algorithm Engineering for Large Graphs

within 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.

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

Algorithms for Ad Hoc Radio Networks

Problems related to Matching

Misc.


People

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/


Some random pictures on BFS, MST, and shortest paths