EUVIMEDEUVIMED entdecken
Crossref

Approximate Distance Sensitivity Oracles in Subquadratic Space

Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, Martin Schirneck

TheoretiCS · 2024

DOI: 10.46298/theoretics.24.15 ↗

Kurz gefasst

Fachartikel in der Zeitschrift TheoretiCS, 2024. Verfasst von Davide Bilò und 6 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

An $f$-edge fault-tolerant distance sensitive oracle ($f$-DSO) with stretch $\sigma \ge 1$ is a data structure that preprocesses a given undirected, unweighted graph $G$ with $n$ vertices and $m$ edges, and a positive integer $f$. When queried with a pair of vertices $s, t$ and a set $F$ of at most $f$ edges, it returns a $\sigma$-approximation of the $s$-$t$-distance in $G-F$. We study $f$-DSOs that take subquadratic space. Thorup and Zwick [JACM 2005] showed that this is only possible for $\sigma \ge 3$. We present, for any constant $f \ge 1$ and $\alpha \in (0, \frac{1}{2})$, and any $\varepsilon > 0$, a randomized $f$-DSO with stretch $ 3 + \varepsilon$ that w.h.p. takes $\widetilde{O}(n^{2-\frac{\alpha}{f+1}}) \cdot O(\log n/\varepsilon)^{f+2}$ space and has an $O(n^\alpha/\varepsilon^2)$ query time. The time to build the oracle is $\widetilde{O}(mn^{2-\frac{\alpha}{f+1}}) \cdot O(\log n/\varepsilon)^{f+1}$. We also give an improved construction for graphs with diameter at most $D$. For any positive integer $k$, we devise an $f$-DSO with stretch $2k-1$ that w.h.p. takes $O(D^{f+o(1)} n^{1+1/k})$ space and has $\widetilde{O}(D^{o(1)})$ query time, with a preprocessing time of $O(D^{f+o(1)} mn^{1/k})$. Chechik, Cohen, Fiat, and Kaplan [SODA 2017] devised an $f$-DSO with stretch $1{+}\varepsilon$ and preprocessing time $O(n^{5+o(1)}/\varepsilon^f)$, albeit with a super-quadratic space requirement. We show how to reduce their preprocessing time to $O(mn^{2+o(1)}/\varepsilon^f)$.

Zitieren

APA

Bilò, D., Chechik, S., Choudhary, K., Cohen, S., Friedrich, T., Krogmann, S., & Schirneck, M. (2024). Approximate Distance Sensitivity Oracles in Subquadratic Space. TheoretiCS. https://doi.org/10.46298/theoretics.24.15

Vancouver

Bilò D, Chechik S, Choudhary K, Cohen S, Friedrich T, Krogmann S, et al. Approximate Distance Sensitivity Oracles in Subquadratic Space. TheoretiCS. 2024. doi:10.46298/theoretics.24.15

BibTeX
@article{Bil2024,
  author = {Bilò, Davide and Chechik, Shiri and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Krogmann, Simon and Schirneck, Martin},
  title = {Approximate Distance Sensitivity Oracles in Subquadratic Space},
  journal = {TheoretiCS},
  year = {2024},
  doi = {10.46298/theoretics.24.15}
}
Kostenlos starten →