Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM
Vignesh Manoharan, Vijaya Ramachandran · 2025
Read Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM by Vignesh Manoharan, Vijaya Ramachandran (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-23604.txt.
Description
Vignesh Manoharan and Vijaya Ramachandran bring a classic network question to parallel computers. A distance sensitivity oracle preprocesses a graph so it can instantly report the shortest path between two points when any single edge fails. The problem matters for communication networks and has been studied heavily for sequential machines and recently for distributed ones, but not for the PRAM model of parallel computation.
The authors present the first PRAM algorithms that build such oracles for directed weighted graphs, answering each query in constant time with one processor after preprocessing. They also give the first work-optimal parallel algorithms for several related problems in the same fine-grained complexity class, including replacement paths, second simple shortest paths, and minimum weight cycles. A brief announcement appeared at SPAA 2025.
Catalog record
| CREATOR | Vignesh Manoharan, Vijaya Ramachandran |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-23604