Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915211518148608 |
|---|---|
| author | Boneh, Itai Chechik, Shiri Golan, Shay Mozes, Shay Weimann, Oren |
| author_facet | Boneh, Itai Chechik, Shiri Golan, Shay Mozes, Shay Weimann, Oren |
| contents | We present a labeling scheme that assigns labels of size $\tilde O(1)$ to the vertices of a directed weighted planar graph $G$, such that for any fixed $\varepsilon>0$ from the labels of any three vertices $s$, $t$ and $f$ one can determine in $\tilde O(1)$ time a $(1+\varepsilon)$-approximation of the $s$-to-$t$ distance in the graph $G\setminus\{f\}$. For approximate distance queries, prior to our work, no efficient solution existed, not even in the centralized oracle setting. Even for the easier case of reachability, $\tilde O(1)$ queries were known only with a centralized oracle of size $\tilde O(n)$ [SODA 21]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_18474 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs Boneh, Itai Chechik, Shiri Golan, Shay Mozes, Shay Weimann, Oren Data Structures and Algorithms Distributed, Parallel, and Cluster Computing We present a labeling scheme that assigns labels of size $\tilde O(1)$ to the vertices of a directed weighted planar graph $G$, such that for any fixed $\varepsilon>0$ from the labels of any three vertices $s$, $t$ and $f$ one can determine in $\tilde O(1)$ time a $(1+\varepsilon)$-approximation of the $s$-to-$t$ distance in the graph $G\setminus\{f\}$. For approximate distance queries, prior to our work, no efficient solution existed, not even in the centralized oracle setting. Even for the easier case of reachability, $\tilde O(1)$ queries were known only with a centralized oracle of size $\tilde O(n)$ [SODA 21]. |
| title | Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2503.18474 |