Algorithm Engineering für große Graphen und Speicherhierarchien

• Applicants: Professor Dr.-Ing. Ulrich Meyer; Professor Dr. Peter Sanders
• Subject Area: Theoretical Computer Science
• Term: from 2001 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5320152

Gegenstand des Projektes ist die systematische Untersuchung grundlegender graphentheoretischer Fragestellungen wie Tiefendurchlauf, Breitendurchlauf, kürzeste Wege, oder aufspannende Bäume mit den Mitteln des Algorithm Engineering, d.h. der integrierten Sichtweise von Entwurf, Analyse, Modellierung, Implementierung und Vermessung von Algorithmen. Ausgangspunkt sind wachsende Lücken zwischen Theorie und Implementierungen auf realen Maschinen vor allem bei Speicherhierarchien (Caches, RAM, Platten) aber auch bei der Wahl des besten Algorithmus für grosse Eingaben. Ziel des Projektes ist es, einige dieser Lücken auszuloten und zu überbrücken. Es sollen neue Algorithmen entwickelt und implementiert werden, die interessante theoretische Ideen in die Praxis umsetzen, in der Praxis verwendete Ansätze mit theoretischen Leistungsgarantien versehen oder Speicherhierarchien geschickt ausnutzen. Ausserdem sollen existierende Verfahren verbessert, effizient implementiert und sorgfältig vermessen werden. Schliesslich sollen die besten Codes Eingang in wiederverwendbare Softwarebibliotheken wie LEDA finden.

• DFG Programme: Priority Programmes
• Subproject of: SPP 1126: Algorithmics of Large and Complex Networks