Am Freitag, den 25. September 2026, verteidigte Jonggang Jiang seine Dissertation mit dem Titel: „Graph Projections for Fast Graph Algorithms”. Seit Oktober 2021 war er Doktorand der Informatik an der Universität des Saarlandes in Saarbrücken und am Max-Planck-Institut für Informatik unter der Betreuung von of Prof. Danupon Na Nongkai, Leiter der Abteilung Algorithms and Complexity. Der Doktorgrad wird von der Universität des Saarlandes verliehen.
Zusammenfassung der Arbeit:
Wir entwickeln Graphprojektionstechniken zur Entwicklung schneller Graphalgorithmen. Anstatt einen Eingabegraphen auf derselben Knotenmenge zu vereinfachen, erweitern wir ihn zu einem größeren Hilfsgraphen mit einfacherer Struktur, lösen das Problem dort und projizieren die Lösung zurück. Dieser Ansatz führt zu vier wesentlichen Beiträgen: DAG-Projektionen für Distanz-, Fluss- und Schnittprobleme, die einen kombinatorischen Algorithmus mit nahezu linearer Laufzeit für den Fluss mit minimalen Kosten in dichten Graphen liefern; Pfadabdeckungen, die den ersten deterministischen Algorithmus mit nahezu linearer Laufzeit für kürzeste Wege mit negativen Gewichten liefern; Clustering nach gemeinsamer Nachbarschaft, das die Lücke zwischen deterministischer und randomisierter Komplexität für den globalen minimalen Knoten-Schnitt schließt und neue parallele sowie verteilte Algorithmen liefert; sowie Steiner-Abkürzungen, die einen möglichen Weg um bekannte Hindernisse für Abkürzungen in gerichteten Graphen aufzeigen. Zusammengenommen zeigen diese Ergebnisse, dass die Erweiterung eines Graphen zu einem größeren, aber strukturierteren Objekt ein wirkungsvolles Prinzip für den Algorithmusentwurf sein kann.