Sehr geehrte Damen und Herren,
ich lade sie herzlich zur Verteidigung meiner Bachelorarbeit mit
dem Titel "Implementing an Algorithm for Routing in Unit Disk
Graphs" betreut von Herrn Prof. Dr. Mulzer ein.
Der Vortrag findet am
Dienstag den 18. 10.
12:00 s.t. (!)
im SR 055 in der Takustr. 9
statt.
mit freundlichen Grüßen,
Christoph Brockmann
Abstract:
During this thesis a new routing scheme for Unit Disk Graphs
described first in Kaplan et al. (2016) was implemented in Python
and tested for performance. In addition, dynamic visualisation of
the routing process was implemented through Mathplotlib allowing
visual inspection of the routing process.
Although experiments show the routing scheme working as intended,
its routing tables scale unfavourably for most graphs that can be
feasibly computed in 2016. It is also shown that for the class of
random graphs presented in this thesis, routing results are much
better than to be expected from the theoretical worst case
considerations in the original paper. Finally, this thesis shows
that the results given in the original paper can be improved
considerably for smaller graphs if 'one-sided' well separated pair
decompositions are used as the basis of the global routing tables.
Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth.
Routing in unit disk graphs.
In LATIN 2016: Theoretical Informatics - 12th Latin American
Symposium, Ensenada, Mexico,
April 11-15, 2016, Proceedings, pages 536–548, 2016.
LyX Document