Wir freuen uns über Ihr Interesse. Wenn Sie überlegen an der Projektgruppe teilzunehmen, schreiben Sie bitte eine unverbindliche formlose Email an Michael Kaibel. Die Projektgruppe hat eine maximale Teilnehmer*innen Anzahl; bitte erwähnen Sie in Ihrer Mail, welche Wahlpflichtfächer in der Algorithmik Sie belegt haben.

Die Inhalte von Algorithmen und Berechnungskomplexität I (insbesondere Laufzeitanalyse, Graphen und grundliegenden Graphalgorithmen, sowie AVL-Bäumen) und Programmierkenntnisse in C++ sind unbedingt erforderlich. Kenntnisse aus der Vorlesung Graphenalgorithmen sind erwünscht.

Gegeben einen ungerichteten Graphen G ist es möglich, in O(n + m) Zeit zu bestimmen, ob zwei Knoten s und t miteinander verbunden sind und, falls sie verbunden sind, einen s-t-Pfad auszugeben. In vielen Kontexten betrachten wir allerdings Graphen, die sich über Zeit verändern. In diesen ist es oft nicht praktikabel, immer wieder eine vollständige Breitensuche o.Ä. auszuführen, insbesondere da das Einfügen und Löschen einer einzigen Kante die Zusammenhangskomponenten des Graphen nicht signifikant verändern kann.

Diese Problematik wird mit sogenannten dynamischen Algorithmen addressiert, die die Intuition “eine einzige Änderung kann die Lösungen nicht so stark beeinflussen” in geschickt konstruierten Datenstrukturen ausnutzen.

Für das dynamische Graph Connectivity Problem wurden bereits eine Vielzahl an Algorithmen entworfen und deren praktische Performance experimentell untersucht. Allerdings haben sowohl theoretische Überlegungen, als auch experimentelle Evaluation bisher darauf beschränkt, die Frage “gibt es einen Pfad zwischen s und t” zu beantworten. Anwendungen von dynamischer Connectivity benötigen aber üblicherweise den tatsächlichen s-t-Pfad, nicht nur die Versicherung, dass er existiert.

Ziel der Projektgruppe ist es, verschiedene Algorithmen für dynamische Connectivity zu modifizieren, sodass diese auch Pfade ausgeben können, und diese Modifikationen in Theorie und experimenteller Evaluation zu vergleichen. Je nach Teilnehmeranzahl werden ggf. auch Algorithmen, die dynamic Connectivity als Subroutine verwenden, implementiert, um eine besonders Anwendungsnahe Evaluation zu ermöglichen. Der Fokus wird dabei insbesondere auf Algorithm Engineering für Graphprobleme gelegt, was die laufzeit- und speichereffiziente Implementation von Algorithmen, ihre experimentelle Evaluation und deren Auswertung beinhaltet.

Die benotete Prüfungsleistung der PG ist ein Vortrag am Ende der Vorlesungszeit und eine schriftliche Ausarbeitung in der die Ergebnisse wissenschaftlich präsentiert werden.

• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Dynamic spanning trees for connectivity queries on fully-dynamic undirected graphs
• An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms

• A Guide to Experimental Algorithmics
• Guidelines for Experimental Algorithmics: A Case Study in Network Analysis
• A Theoretician’s Guide to the Experimental Analysis of Algorithms

_{DozentInnen: Mutzel, Kaibel}