This thesis addresses the decremental All-Pairs Shortest Paths (APSP) problem in dynamic graphs, where edges are only removed over time. Since static algorithms require a full recomputation after each change, they are inefficient for dynamic networks. Approximation approaches resolve this by trading exactness for significantly faster maintenance of distances.
We implemented and compared four algorithms: the exact ES-tree algorithm, Krinninger's randomized and deterministic algorithms, and Dory's algorithm. We tested the algorithms on synthetic graphs (Erdős-Rényi, Barabási-Albert, tree-like, and regular) and compared them with respect to construction time, memory usage, and approximation accuracy.
The ES-tree algorithm returns exact distances but is the most resource-intensive. Krinninger's randomized algorithm is fastest on sparse graphs, but its distance emulator exceeds the original graph size on dense graphs. Krinninger's deterministic algorithm is the most robust, achieving higher accuracy across all graph types. Dory's algorithm is memory-efficient for graphs with small diameter, but requires the diameter to be known in advance and returns infinite distance for pairs outside the specified depth.
We further optimized Krinninger's deterministic algorithm. Checking distances up to 2 yielded the largest accuracy improvement. Incremental greedy center selection and a center dictionary together sped up construction by ~30 %, deletion by ~80 %, and queries by ~40 %. Parallel construction with 4 processes adds another 40-55 % speed up for n = 2000. An experiment in which we deleted up to 50 % of edges confirmed that the algorithm maintains its approximation guarantee across all test scenarios.
|
