Título: A simple yet effective algorithm to compute incremental All-pairs Shortest Distances
Arturo Vebel De León (Universidad Distrital Francisco José de Caldas)
Jueves 3 de Junio, 11:00 - 12:00 pm
We build upon the naive algorithm that visits all pairs of nodes comparing if the new shortcut shortens the distances, and propose a simple variation that instead chooses pairs of source and target nodes, only from the affected shortest paths. The new algorithm works with an optimal data structure, constant query time and worst-case O(n^2) update cost, although our results on synthetic datasets hints at its practicality when compared with state-of-the-art approaches.