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

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

And next week on Tuesday

------------------------ Ursprüngliche Nachricht ------------------------
Betreff: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit
Von:     "Christoph Brockmann" <chbrock@zedat.fu-berlin.de>
Datum:   Di, Oktober 11, 2016 11:12
An:      i-studi@inf.fu-berlin.de
         i-wimis@inf.fu-berlin.de
         i-profs@inf.fu-berlin.de
         "Wolfgang Mulzer" <mulzer@inf.fu-berlin.de>
         "Zentiks, Sera Renee" <SeraRenee.Zentiks@fu-berlin.de>
--------------------------------------------------------------------------

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

LyX Document

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

Title: LyX Document

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.