Incremental FO(+,<) Maintenance of All-Pairs Shortest Paths for Undirected Graphs After Insertions and Deletions
Find in a Library
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.
& Dong, G.
(1999). Incremental FO(+,<) Maintenance of All-Pairs Shortest Paths for Undirected Graphs After Insertions and Deletions. Database Theory--ICDT'99: 7th International Conference, Jerusalem, Israel, January 10-12, 1999: Proceedings, 365-382.