# Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality

Preprint · Meghana Nasre, Matteo Pontecorvi, Vijaya Ramachandran

- Archive id: arxiv:1411.4073
- Published: 2014-11-14
- arXiv: https://arxiv.org/abs/1411.4073
- Citations: 1
- Source URL: https://arxiv.org/abs/1411.4073
- PDF: https://arxiv.org/pdf/1411.4073
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.