A fundamental question in graph theory is the Single-Source Shortest Path (sssp) problem. This is well-studied in classical algorithm literature, but is only more recently studied in the parallel setting. A relatively...
详细信息
A fundamental question in graph theory is the Single-Source Shortest Path (sssp) problem. This is well-studied in classical algorithm literature, but is only more recently studied in the parallel setting. A relatively simple way to solve sssp in parallel is with a Parallel Bellman-Ford(BF). BF shows strong performance on dense graphs, when m >> n. But due to its frontier-based approached, BF is bounded by the diameter of the graph. This thesis proposes 2 different preprocessing strategies to alleviate this. The first strategy is to generate shortcuts such that each vertex attempts to have at most degree k. The second approach is graph contraction, which removes specific vertices and replaces them with a single shortcut. We show that both preprocessing strategies reduce the overall rounds required to complete all testing algorithms. Additionally, we evaluate both preprocessing strategies with our own implementation of BF and state of the art parallel sssp algorithms. In general, δ-stepping and ρ-stepping show improved times after contraction.
暂无评论