Springe direkt zu Inhalt

Disputation Katharina Alexandra Klost

21.09.2021 | 16:00
Thema der Dissertation:
Geometric Graphs: Reachability, Long Trees and Short Cycles
Thema der Disputation:
Shortest Paths in Unit Disk Graphs
Abstract: Unit disk graphs are a common and extensively studied model for wireless networks. In a unit disk graph, the vertices are defined by a set of points in the plane, and two vertices are connected with an edge if and only if their distance is at most 1.
The length of a path between two vertices in a unit disk graph can be defined either as the number of edges on the path, or as the sum of the distances of the vertices on the path. In the first case, we talk about "unweighted" unit disk graphs, while in the second case, we talk about "weighted" unit disk graphs.
The single source shortest path problem in a graph asks for the shortest path tree rooted at a start vertex. In general unweighted graphs the problem is usually solved efficiently by using breadth first search. In weighted graphs with positive real weights, Dijkstra's algorithm and variants thereof are used.
We consider the single source shortest path problem in both unweighted and weighted unit disk graphs. We describe the algorithms of Chan and Skrepetos, and Efrat et al. for the unweighted case and consider their similarities and differences. Furthermore we take a look at the algorithm of Wang and Xue for the weighted case and again compare the techniques used with those for the unweighted case.

Zeit & Ort

21.09.2021 | 16:00

gr. Hörsaal* (Takustr.9, 14195 Berlin)
* Begrenzte Teilnehmerzahl unter Kontrolle der 3G Regeln – geimpft, genesen, getestet