Bibliography | Epple, Lukas: Computing shortest path distances based on cluster-pairs. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 35 (2021). 44 pages, english.
|
Abstract | In this thesis we present a new lookup based shortest path distance computation scheme. Like many other lookup based schemes, this new approach consists of two stages, a preprocessing and a query stage. After the properties, which need to be met by the results of the preprocessing, are formally defined, we propose different preprocessing procedures as well as procedures which are able to use those results to calculate shortest path distances. The proposed new query procedure is able to decide whether a given query can be answered when the preprocessed data is incomplete. This makes it possible to prune the preprocessed data according to arbitrary memory constraints, while a speed up of orders of magnitude in comparison to conventional techniques can be achieved.
|
Full text and other links | Volltext
|
Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
|
Superviser(s) | Funke, Prof. Stefan |
Entry date | November 4, 2021 |
---|