Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2411.13728 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915613169942528 |
|---|---|
| author | Manoharan, Vignesh Ramachandran, Vijaya |
| author_facet | Manoharan, Vignesh Ramachandran, Vijaya |
| contents | We present results for the distance sensitivity oracle (DSO) problem, where one needs to preprocess a given directed weighted graph $G=(V,E)$ in order to answer queries about the shortest path distance in $G$ from vertex $s$ to vertex $t$ avoiding edge $e$, for any $s,t \in V, e \in E$. DSO enables optimal re-routing under a link failure, and can serve as a key component for fault tolerance in a distributed setting. However, no non-trivial results for DSO are known in the distributed CONGEST model.
We present DSO algorithms with different tradeoffs between preprocessing and query cost: one that optimizes query response rounds, and another that prioritizes preprocessing rounds. We complement these algorithms with unconditional CONGEST lower bounds for DSO. Our DSO lower bounds build on a lower bound we present for the $k$-source shortest paths problem ($k$-SSP), which may be of independent interest. Additionally, we present almost-optimal upper and lower bounds for the related all pairs second simple shortest path (2-APSiSP) problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_13728 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distributed Distance Sensitivity Oracles Manoharan, Vignesh Ramachandran, Vijaya Data Structures and Algorithms We present results for the distance sensitivity oracle (DSO) problem, where one needs to preprocess a given directed weighted graph $G=(V,E)$ in order to answer queries about the shortest path distance in $G$ from vertex $s$ to vertex $t$ avoiding edge $e$, for any $s,t \in V, e \in E$. DSO enables optimal re-routing under a link failure, and can serve as a key component for fault tolerance in a distributed setting. However, no non-trivial results for DSO are known in the distributed CONGEST model. We present DSO algorithms with different tradeoffs between preprocessing and query cost: one that optimizes query response rounds, and another that prioritizes preprocessing rounds. We complement these algorithms with unconditional CONGEST lower bounds for DSO. Our DSO lower bounds build on a lower bound we present for the $k$-source shortest paths problem ($k$-SSP), which may be of independent interest. Additionally, we present almost-optimal upper and lower bounds for the related all pairs second simple shortest path (2-APSiSP) problem. |
| title | Distributed Distance Sensitivity Oracles |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.13728 |