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

CREATORVignesh Manoharan, Vijaya Ramachandran
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-23604

Browse the full library · About the Tower of Babel