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.
Abstract
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.