Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.23604 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911346556141568 |
|---|---|
| author | Manoharan, Vignesh Ramachandran, Vijaya |
| author_facet | Manoharan, Vignesh Ramachandran, Vijaya |
| contents | The distance sensitivity oracle (DSO) problem asks us to preprocess a given graph $G=(V,E)$ in order to answer queries of the form $d(x,y,e)$, which denotes the shortest path distance in $G$ from vertex $x$ to vertex $y$ when edge $e$ is removed. This is an important problem for network communication, and it has been extensively studied in the sequential settingand recently in the distributed CONGEST model. However, no prior DSO results tailored to the parallel setting were known.
We present the first PRAM algorithms to construct DSOs in directed weighted graphs, that can answer a query in $O(1)$ time with a single processor after preprocessing. We also present the first work-optimal PRAM algorithms for other graph problems that belong to the sequential $\tilde{O}(mn)$ fine-grained complexity class: Replacement Paths, Second Simple Shortest Path, All Pairs Second Simple Shortest Paths and Minimum Weight Cycle. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_23604 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM Manoharan, Vignesh Ramachandran, Vijaya Data Structures and Algorithms The distance sensitivity oracle (DSO) problem asks us to preprocess a given graph $G=(V,E)$ in order to answer queries of the form $d(x,y,e)$, which denotes the shortest path distance in $G$ from vertex $x$ to vertex $y$ when edge $e$ is removed. This is an important problem for network communication, and it has been extensively studied in the sequential settingand recently in the distributed CONGEST model. However, no prior DSO results tailored to the parallel setting were known. We present the first PRAM algorithms to construct DSOs in directed weighted graphs, that can answer a query in $O(1)$ time with a single processor after preprocessing. We also present the first work-optimal PRAM algorithms for other graph problems that belong to the sequential $\tilde{O}(mn)$ fine-grained complexity class: Replacement Paths, Second Simple Shortest Path, All Pairs Second Simple Shortest Paths and Minimum Weight Cycle. |
| title | Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.23604 |