Back to Search
Start Over
Efficient Maintenance of Shortest Distances in Dynamic Graphs.
- Source :
-
IEEE Transactions on Knowledge & Data Engineering . Mar2018, Vol. 30 Issue 3, p474-487. 14p. - Publication Year :
- 2018
-
Abstract
- Computing shortest distances is a central task in many domains. The growing number of applications dealing with dynamic graphs calls for incremental algorithms, as it is impractical to recompute shortest distances from scratch every time updates occur. In this paper, we address the problem of maintaining all-pairs shortest distances in dynamic graphs. We propose efficient incremental algorithms to process sequences of edge deletions/insertions/updates and vertex deletions/insertions. The proposed approach relies on some general operators that can be easily “instantiated” both in main memory and on top of different underlying DBMSs. We provide complexity analyses of the proposed algorithms. Experimental results on several real-world datasets show that current main-memory algorithms become soon impractical, disk-based ones are needed for larger graphs, and our approach significantly outperforms state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPHIC methods
*ALGORITHMS
*NUMERICAL analysis
*MATHEMATICAL analysis
*DATABASES
Subjects
Details
- Language :
- English
- ISSN :
- 10414347
- Volume :
- 30
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Knowledge & Data Engineering
- Publication Type :
- Academic Journal
- Accession number :
- 127814369
- Full Text :
- https://doi.org/10.1109/TKDE.2017.2772233