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

Authors

Chaoyi Pang
Kotagiri Ramamohanarao
Guozhu Dong, Wright State University - Main CampusFollow

Document Type

Book Chapter

Publication Date

1999

Find in a Library

Catalog Record

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²) number of tuples, where n is the number of vertices, and have AC⁰ 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.

Comments

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

Repository Citation

Pang, C., Ramamohanarao, K., & 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.
https://corescholar.libraries.wright.edu/knoesis/349