All-pairs shortest distances maintenance in relational DBMSs
Sergio Greco, Cristian Molinaro, Chiara Pulice, Ximena Quintana · Advances in Social Networks Analysis and Mining · 2016
Computing shortest distances is a central task in many graph applications. Although many algorithms to solve this problem have been proposed, they are designed to work in the main memory and/or with static graphs, which limits their applicability to many current applications where graphs are subject to frequent updates. In this paper, we propose novel efficient incremental algorithms for maintaining all-pairs shortest distances in dynamic graphs. We experimentally evaluate our approach on real-world datasets, showing that it outperforms current algorithms designed for the same problem.