{"id":"arxiv:1412.3852","kind":"preprint","title":"Fully Dynamic All Pairs All Shortest Paths","authors":["Matteo Pontecorvi","Vijaya Ramachandran"],"author_count":2,"year":2014,"published":"2014-12-11","venue":null,"cited_by":5,"doi":null,"arxiv_id":"1412.3852","nct_id":null,"source_url":"https://arxiv.org/abs/1412.3852","archive_url":"https://space-kitty.com/papers/arxiv:1412.3852","updated":"2022-04-20","pmid":null,"pmcid":null,"openalex_id":"W1538731881","pdf_url":"https://arxiv.org/pdf/1412.3852","abstract":"We consider the all pairs all shortest paths (APASP) problem, which maintains all of the multiple shortest paths for every vertex pair in a directed graph $G=(V,E)$ with a positive real weight on each edge. We present two fully dynamic algorithms for this problem in which an update supports either weight increases or weight decreases on a subset of edges incident to a vertex. Our first algorithm runs in amortized $O({ν^*}^2 \\cdot \\log^3 n)$ time per update, where $n = |V|$, and $ν^*$ bounds the number of edges that lie on shortest paths through any single vertex. Our APASP algorithm leads to the same amortized bound for the fully dynamic computation of betweenness centrality (BC), which is a parameter widely used in the analysis of large complex networks. Our method is a generalization and a variant of the fully dynamic algorithm of Demetrescu and Italiano [DI04] for unique shortest path, and it builds on our recent decremental APASP [NPR14]. Our second (faster) algorithm reduces the amortized cost per operation by a logarithmic factor, and uses new data structures and techniques that are extensions of methods in a fully dynamic algorithm by Thorup.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[{"slug":"algorithms-complexity","name":"Algorithms & Complexity Breakthroughs","domain_slug":"math-cs"}],"cited_in_dossiers":[]}