Logo des Repositoriums
 

Algorithmen für graphbasierte dynamische Probleme

dc.contributor.authorGoranci, Gramoz
dc.contributor.editorHölldobler, Steffen
dc.date.accessioned2022-01-24T12:37:16Z
dc.date.available2022-01-24T12:37:16Z
dc.date.issued2020
dc.description.abstractEin 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.de
dc.identifier.isbn978-3-88579-775-3
dc.identifier.urihttps://dl.gi.de/handle/20.500.12116/38001
dc.language.isode
dc.publisherGesellschaft für Informatik e.V.
dc.relation.ispartofAusgezeichnete Informatikdissertationen 2019
dc.relation.ispartofseriesLecture Notes in Informatics (LNI) - Proceedings, Volume D-20
dc.titleAlgorithmen für graphbasierte dynamische Problemede
dc.typeText/Conference Paper
gi.citation.endPage108
gi.citation.publisherPlaceBonn
gi.citation.startPage99
gi.conference.date17.-20. Mai 2020
gi.conference.locationSchoss Dagstuhl, Deutschland

Dateien

Originalbündel
1 - 1 von 1
Lade...
Vorschaubild
Name:
Goranci_Gramoz.pdf
Größe:
414.47 KB
Format:
Adobe Portable Document Format