Incremental FO(+,<) Maintenance of All-pairs Shortest Paths for Undirected Graphs After Insertions and Deletions

Chaoyi Pang, The University of Melbourne

Ramamohanarao Kotagiri, The University of Melbourne

Guozhu Dong, The University of Melbourne

Proceedings of International Conference on Database Theory, Jerusalem, January, 1999.


We give incremental algorithms, which support both edge insertions and deletions, for the all-pairs shortest-distance problem (APSD) in weighted undirected graphs. Our algorithms use first-order queries, $+$ (addition) and $<$ (less-than); they store $O(n^2)$ number of tuples, where $n$ is the number of vertices, and have $AC^0$ data complexity for integer weights. Since $FO(+,<)$ is supported by almost all current database systems, our maintenance algorithms are more appropriate for database applications than non-database query type of maintenance algorithms. Our algorithms can also be extended to duplicate semantics.