Algorithmen für graphbasierte dynamische Probleme

Abstract

Ein dynamischer Graphalgorithmus ist eine Datenstruktur, die einen Graphen speichert, der sich über die Zeit ändert, und die die Lösung für ein zugrunde liegendes Graphproblem nach jeder Änderung effizient aktualisiert. Ein Graph-Sparsifier ist eine komprimierte Darstellung eines großen Eingabegraphen, bei dem einige Grapheigenschaften (annähernd) erhalten bleiben. In dieser Dissertation entwickeln wir neue Techniken sowohl für dynamische Graphalgorithmen als auch für Sparsifikationsalgorithmen. Wir fokussieren uns auf verschiedene graphbasierte Optimierungsprobleme, die in der spektralen Graphentheorie, der Graphpartitionierung und bei metrischen Einbettungen auftreten. Unsere dynamische Algorithmen haben schnellere Laufzeiten als vorherige Ergebnisse. Unsere Sparsifier-Konstruktionen erzeugen kleinere Sparsifier und verbessern gleichzeitig ihre Approximationsqualität. Wir führen zudem neuartige Reduktionstechniken ein, die unerwartete Zusammenhänge zwischen dynamischen Graphalgorithmen und sparsifizierten Graphen aufdecken.