Algorithmik großer und komplexer Netzwerke

In der heutigen Gesellschaft spielt Vernetzung eine Schlüsselrolle. Informationsverbreitung, Kommunikation, Mobilität und Transport basieren ebenso auf Netzwerken wie das soziale und politische Handeln von Organisationen und Personen. In vielen Forschungsgebieten wird mit Netzwerken gearbeitet bzw. werden Netzwerke untersucht. Die Umsetzung dieser Anstrengungen auf konkrete Probleme wird praktisch immer mit Rechnern realisiert. Der Algorithmik als einer der Grundlagen der Informatik und gleichzeitigem Bindeglied zur Mathematik wird dabei eine Schlüsselrolle zuteil, da sie wie kaum ein anderes Gebiet Querverbindungen zwischen verschiedenen Bereichen herstellt. Fortschritte bei der Entwicklung von algorithmischen Lösungen für Netzwerkprobleme haben Konsequenzen für alle mit Netzwerken befassten Disziplinen; sie sind notwendige Voraussetzung für deren Erfolg.

Um die Abläufe und Funktionsweisen innerhalb von Netzwerken zu beherrschen, müssen wir die dahinterliegenden abstrakten Strukturen verstehen. Dazu gehört die effiziente algorithmische Lösung grundlegender Problemstellungen in Netzwerken ebenso wie deren strukturelle Analyse und geeignete Visualisierung. Die Algorithmik auf Netzwerken bzw. Graphen ist innerhalb der Mathematik und Informatik ein klassisches Thema, dessen Grundlagen bereits gut untersucht sind. Graphenalgorithmen gehören zu den ältesten Verfahren in der Algorithmentheorie. Grundlegende Graphenalgorithmen wie kürzeste-Wege-Algorithmen oder Flussalgorithmen werden in der Praxis angewendet. Jedoch wird das Potential algorithmischer Verfahren bei weitem noch nicht ausgeschöpft. Selbst das Verhalten vieler theoretisch gut analysierter Algorithmen ist für große und komplexe Datenmengen konkrete Anwendungsprobleme bzw. echte Anwendungsdaten kaum erforscht. Angesichts des rasanten Wachstums anwendungsbasierter Netze - man denke nur an Netzwerke im Verkehrsbereich oder das WWW - ist weit mehr als die Adaption bekannter Verfahren erforderlich. An dieser Stelle soll das Schwerpunktprogramm durch eine gezielte Weiterentwicklung anwendungsmotivierter, methodischer Forschung eingreifen.

Ziel dieses Schwerpunktprogramms ist es, die Forschung in der Algorithmik voranzutreiben und deren Anwendungspotential zu erweitern. Grundlegende Methoden der Algorithmentheorie sollen unter dem Blickwinkel aktueller, durch Anwendungen geprägter Aspekte weiterentwickelt werden. Bewusst wird mit der Ausrichtung auf netzwerkbasierte Probleme ein algorithmisches Gebiet fokussiert, das einerseits aufgrund seiner vielfältigen Anwendungen von großer Relevanz ist, andererseits in besonderer Weise neue algorithmische Aspekte und aktuelle methodische Entwicklungen der Algorithmik widerspiegelt. Die Erschließung neuer diskreter algorithmischer Methoden ist vor allem durch die Fokussierung auf große und komplexe Netzwerke zu erwarten. Neue Erkenntnisse in diesem Zusammenhang werden sich auch auf andere algorithmische Bereiche und entsprechende Anwendungsgebiete übertragen lassen. Für einige der hier angesprochenen Probleme sind zwar Lösungsvorschläge greifbar, allerdings sind diese meist unbefriedigend, wenn nicht sogar schlecht. Es geht darum, bessere, methodisch wohldurchdachte und langfristig wirksame Lösungen zu entwickeln.

Nicht zuletzt wegen der ausdrücklich gewünschten Orientierung des Schwerpunktprogramms an Fragestellungen aus konkreten Anwendungen ist eine Einbeziehung von Methoden des Algorithm Engineering geplant, einem sehr jungen Teilgebiet der Algorithmik, das alle Aspekte der tatsächlichen praktischen Umsetzbarkeit von Algorithmen, angefangen bei der mathematischen Modellierung von Anwendungsproblemen, über den theoretischen Algorithmenentwurf und die Algorithmenimplementation, bis hin zum empirischen Algorithmenentwurf, der experimentellen Erforschung von Algorithmen und der systematischen Untersuchung des Verhaltens von Algorithmen bei Praxisdaten umfasst. Erst seit wenigen Jahren finden derartige Themen verstärkt Eingang in die algorithmisch orientierte Forschung. Das geplante Schwerpunktprogramm soll diese Entwicklung weiter vorantreiben.

Durch das Programm soll eine gegenseitige Befruchtung zwischen verschiedenen Projekten forciert werden. Es ermöglicht den wechselseitigen Austausch zwischen konkreten, aus Anwendungen motivierten Projekten und übergreifenden Querschnittsprojekten.