[Mittagsseminar TI] Fwd: [Ml-iwimi-mi] Einladung zur Verteidigung meiner Bachelorarbeit

[Katharina Klost <kathklost@zedat.fu-berlin.de>]

This thesis defense is tomorrow in the noon seminar (the talk will be in German)

-------- Weitergeleitete Nachricht --------

Betreff:	[Ml-iwimi-mi] Einladung zur Verteidigung meiner Bachelorarbeit
Datum:	Thu, 14 Dec 2023 16:32:57 +0100
Von:	"Yagmur Dönmez" <yagmud01@zedat.fu-berlin.de>
An:	i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de, i-studi@inf.fu-berlin.de, maria.koekenhoff@fu-berlin.de

Sehr geehrte Damen und Herren,
ich lade Sie hiermit herzlich zu Verteidigung meiner Bachelorarbeit mit
dem Titel "Vergleich der Streaming und Online Algorithmen für das
Kantenfärbungsproblem" ein.
Der Vortrag wird am 21.12.23 um 12:00 Uhr in der Takustraße 9 Raum 051
stattfinden.

Erstgutachter: Dr. rer. nat. Katharina Klost
Zweitgutachter: Prof. Dr. László Kozma

Mit freundlichen Grüßen
Yagmur Dönmez

Abstract
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.

_______________________________________________
Automatischer Mailverteiler an Gruppe 'ml-iwimi-mi'.
Hinweise dazu siehe Hilfeseite:
https://www.mi.fu-berlin.de/w/Tec/AnkuendigungsVerteiler