Springe direkt zu Inhalt

Yagmur Dönmez:

Vergleich der Streaming und Online Algorithmen für das Kantenfärbungsproblem

Kurzbeschreibung

Die Kantenfärbung zählt zu den fundamentalsten Problemen innerhalb der Graphentheorie. Im Streaming Modell werden die Kanten des Eingabegraphen dem Algorithmus einzeln präsentiert. Hierbei ist der zur Verfügung stehende Speicher kleiner als die Größe des Eingabegraphen, weshalb nicht alle Kanten des Graphen gespeichert werden können. Da die Ausgabe genauso groß ist wie die Eingabe selbst, müssen auch die Farben der Kanten als Stream ausgegeben werden, das sogenannte W-Streaming. In der Vergangenheit wurden schon einige Lösungen für dieses Problem in verschiedensten Modellen vorgestellt. In dieser Arbeit werden wir uns die Entwicklung und Fortschritte dieser genauer anschau- en. Zuletzt lieferten zwei randomisierte Algorithmen im gegnerischen Kantenan- kunftsmodell, aus ESA 2019, SOSA 2021 und ESA 2022, die besten Ergebnisse. Hierbei färbt der neueste jeden Graphen mit 2∆t Farben in O(n∆/t) Platz für jedes n ≤ ∆, wobei ∆ der maximale Grad des Graphen ist. Diese Lösung bietet den einzigen bekannten Online-Kantenfärbungsalgorithmus mit sublinearem Platzbedarf. Unser Ziel ist es die verschiedenen Ergebnisse mit einander zu vergleichen, um potenzielle Verbesserungen zu identifizieren.

Abschluss
Bachelor of Science (B.Sc.)
Abgabedatum
21.12.2023