[Mittagsseminar TI] FW: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

Dear TIs,

This is tomorrow's Mittagsseminar. 

The talk will be given in German.

Cheers 

Wolfgang 

-------- Ursprüngliche Nachricht --------

Von: Janos Lohan <janol55@zedat.fu-berlin.de>

Datum: 11.08.25 12:19 (GMT+01:00)

An: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de, i-studi@inf.fu-berlin.de, maria.koekenhoff@fu-berlin.de

Betreff: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit

Sehr geehrte Damen und Herren,

hiermit lade ich Sie herzlich zur Verteidigung meiner Bachelorarbeit zum
Thema "Übertragung von Tree Cover auf die Kürzeste-Wege-Metrik von Unit
Disk Graphen" ein.
Die Verteidigung findet am Donnerstag, den 14.08.2025, um 12:00 Uhr im
Raum 055 der Takustraße 9 statt.

Betreuer/Erstgutachter: Prof. Dr. Wolfgang Mulzer
Zweitgutachter: Dr. Max Willert

Mit freundlichen Grüßen
Janos Lohan

Abstract:

In dieser Arbeit wird die Übertragung des Konzepts des Tree Covers auf die
Kürzeste-Wege-Metrik von Unit Disk Graphen untersucht.

Ein α-Tree Cover ist eine Überdeckung eines Graphen durch eine Menge von
Bäumen. Für jedes Knotenpaar muss dabei ein Baum aus dem Tree Cover
existieren, in dem die Kürzeste-Wege-Distanz um höchstens den Faktor α
verzerrt wird. Viele Distanzprobleme lassen sich auf dieser Menge von
Bäumen anstelle des ursprünglichen Graphen effizient approximieren.

Für die euklidische Metrik, Metriken mit konstanter Doubling Dimension und
planare Graphen existieren bereits effiziente Algorithmen zur Konstruktion
kompakter Tree Cover. Es wird untersucht, inwieweit sich diese Ansätze auf
die Kürzeste-Wege-Metrik von Unit Disk Graphen übertragen lassen.
Anschließend wird ein eigener Algorithmus zur Konstruktion eines Tree
Covers auf Unit Disk Graphen vorgestellt, der auf einer Well-Separated
Pair Decomposition basiert. Das resultierende Tree Cover wird analysiert
und mit den bestehenden Verfahren anderer metrischer Räume verglichen.

Für dichte oder gleichmäßig verteilte Unit Disk Graphen wird dabei im
schlechtesten Fall ein (1+ε)-Tree Cover mit konstantem Verzerrungsfaktor
in subquadratischer Zeit konstruiert, wobei subquadratisch viele Kanten
gespeichert werden müssen. Zudem lässt sich für jedes Punktepaar in
konstanter Zeit ein passender Baum finden, der die Distanz minimal
verzerrt, sodass das Tree Cover für effizientes Routing in zum Beispiel
Ad-hoc-Netzwerken angewendet werden kann.

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