Algorithm Engineering für große Graphen und Speicherhierarchien

• Antragsteller: Professor Dr.-Ing. Ulrich Meyer; Professor Dr. Peter Sanders
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2001 bis 2008
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1126: Algorithmik großer und komplexer Netzwerke