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