Logo des Repositoriums

D20 (2019) - Ausgezeichnete Informatikdissertationen

https://dl.gi.de/handle/20.500.12116/37999
Auflistung nach:

Auflistung D20 (2019) - Ausgezeichnete Informatikdissertationen nach Autor:in "Goranci, Gramoz"

1 - 1 von 1
  • Konferenzbeitrag
    Algorithmen für graphbasierte dynamische Probleme
    (Ausgezeichnete Informatikdissertationen 2019, 2020) Goranci, Gramoz
    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.