Fault-Tolerant Approximate Distance Oracles with a Source Set
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911252919353344 |
|---|---|
| author | Dey, Dipan Kavitha, Telikepalli |
| author_facet | Dey, Dipan Kavitha, Telikepalli |
| contents | Our input is an undirected weighted graph $G = (V,E)$ on $n$ vertices along with a source set $S\subseteq V$. The problem is to preprocess $G$ and build a compact data structure such that upon query $Qu(s,v,f)$ where $(s,v) \in S\times V$ and $f$ is any faulty edge, we can quickly find a good estimate (i.e., within a small multiplicative stretch) of the $s$-$v$ distance in $G-f$.
The work of Bil{ò} et al. (Algorithmica 2022) on multiple-edge fault-tolerant approximate shortest path trees implies a compact oracle for the above problem with a stretch of at most 3 and with query answering time $O(\log^2 n)$. We show a very simple construction of an $S\times V$ approximate distance oracle with $O(1)$ query answering time; its size is $\widetilde{O}(|S|n + n^{3/2})$ and multiplicative stretch is at most 5. A single-edge fault-tolerant $ST$-distance oracle from the work of Bil{ò} et al. (STACS 2018) plays a key role in our construction. We also give a construction of a fault-tolerant $S \times V$ approximate distance oracle of size $\widetilde{O}(|S|n + n^{4/3})$ with multiplicative stretch at most 13 and as before, with $O(1)$ query answering time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_01239 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fault-Tolerant Approximate Distance Oracles with a Source Set Dey, Dipan Kavitha, Telikepalli Data Structures and Algorithms Our input is an undirected weighted graph $G = (V,E)$ on $n$ vertices along with a source set $S\subseteq V$. The problem is to preprocess $G$ and build a compact data structure such that upon query $Qu(s,v,f)$ where $(s,v) \in S\times V$ and $f$ is any faulty edge, we can quickly find a good estimate (i.e., within a small multiplicative stretch) of the $s$-$v$ distance in $G-f$. The work of Bil{ò} et al. (Algorithmica 2022) on multiple-edge fault-tolerant approximate shortest path trees implies a compact oracle for the above problem with a stretch of at most 3 and with query answering time $O(\log^2 n)$. We show a very simple construction of an $S\times V$ approximate distance oracle with $O(1)$ query answering time; its size is $\widetilde{O}(|S|n + n^{3/2})$ and multiplicative stretch is at most 5. A single-edge fault-tolerant $ST$-distance oracle from the work of Bil{ò} et al. (STACS 2018) plays a key role in our construction. We also give a construction of a fault-tolerant $S \times V$ approximate distance oracle of size $\widetilde{O}(|S|n + n^{4/3})$ with multiplicative stretch at most 13 and as before, with $O(1)$ query answering time. |
| title | Fault-Tolerant Approximate Distance Oracles with a Source Set |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.01239 |