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

Document Type

Book Chapter

Publication Date


Find in a Library

Catalog Record


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 (n2) number of tuples, where n is the number of vertices, and have AC0 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 maintenance algorithms. Our algorithms can also be extended to duplicate semantics.


Paper presented at the 7th International Conference on Database Theory, Jerusalem, Israel, January 10-12, 1999.

Catalog Record