Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality

DOI10.1007/978-3-319-13075-0_60MaRDI QIDQ2942677zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Meghana Nasre, Matteo Pontecorvi, Vijaya Ramachandran

Publication date 11 September 2015

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.4073

zbMATH Keywords

all pairs all shortest paths problem

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38)

Abstract: We consider the all pairs all shortest paths (APASP) problem, which maintains the shortest path dag rooted at every vertex in a directed graph G=(V,E) with positive edge weights. For this problem we present a decremental algorithm (that supports the deletion of a vertex, or weight increases on edges incident to a vertex). Our algorithm runs in amortized O(vstar^2 cdot log n) time per update, where n=|V|, and vstar bounds the number of edges that lie on shortest paths through any given vertex. Our APASP algorithm can be used for the decremental computation of betweenness centrality (BC), a graph parameter that is widely used in the analysis of large complex networks. No nontrivial decremental algorithm for either problem was known prior to our work. Our method is a generalization of the decremental algorithm of Demetrescu and Italiano [DI04] for unique shortest paths, and for graphs with vstar =O(n), we match the bound in [DI04]. Thus for graphs with a constant number of shortest paths between any pair of vertices, our algorithm maintains APASP and BC scores in amortized time O(n^2 log n) under decremental updates, regardless of the number of edges in the graph.

Recommendations

• Decremental all-pairs shortest paths in deterministic near-linear time
• All-Pairs Almost Shortest Paths
• Betweenness centrality -- incremental and faster
• Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
• Exact and approximate algorithms for computing betweenness centrality in directed graphs
• Enumerating shortest paths and determining edge betweenness centrality in Cartesian products of paths and cycles
• All-pairs shortest paths and the essential subgraph
• Fully-dynamic approximation of betweenness centrality
• An all pairs shortest path algorithm for dynamic graphs
• Maximum betweenness centrality: approximability and tractable cases

Cited in

(2)

• The sparsest additive spanner via multiple weighted BFS trees
• Fully dynamic betweenness centrality

This page was built for publication: Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942677)