Parallel Pruned Landmark Labeling for Shortest Path Queries on Unit-Weight Networks

While using graphs inside of an application, there is often a need to repeatedly answer shortest-path distance queries between pairs of vertices. There are numerous ways to solve this problem. In this thesis, we present an approach that utilizes the research done within labeling-based methods, which represent a compromise between online-search-based methods (e.g., Breadth-First-Search) and transitive-closure-based methods (e.g., by using Floyd-Warshall), and thread-parallelism. Our focus within this thesis is to introduce an approach that scales well in a multi-threaded environment. It is based on a two-phased labeling method as found in [AIY13]; this method also forms a baseline for our comparisons. Additionally, we present general performance measures and discuss the scaling behaviour of our approach.