English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

An $f$-edge fault-tolerant distance sensitive oracle ($f$-DSO) with stretch$\sigma \geq 1$ is a data structure that preprocesses an input graph $G$. Whenqueried with the triple $(s,t,F)$, where $s, t \in V$ and $F \subseteq E$contains at most $f$ edges of $G$, the oracle returns an estimate$\widehat{d}_{G-F}(s,t)$ of the distance $d_{G-F}(s,t)$ between $s$ and $t$ inthe graph $G-F$ such that $d_{G-F}(s,t) \leq \widehat{d}_{G-F}(s,t) \leq \sigmad_{G-F}(s,t)$. For any positive integer $k \ge 2$ and any $0 < \alpha < 1$, wepresent an $f$-DSO with sensitivity $f = o(\log n/\log\log n)$, stretch $2k-1$,space $O(n^{1+\frac{1}{k}+\alpha+o(1)})$, and an$\widetilde{O}(n^{1+\frac{1}{k} - \frac{\alpha}{k(f+1)}})$ query time.  Prior to our work, there were only three known $f$-DSOs with subquadraticspace. The first one by Chechik et al. [Algorithmica 2012] has a stretch of$(8k-2)(f+1)$, depending on $f$. Another approach is storing an $f$-edgefault-tolerant $(2k-1)$-spanner of $G$. The bottleneck is the large query timedue to the size of any such spanner, which is $\Omega(n^{1+1/k})$ under theErd\H{o}s girth conjecture. Bil\`o et al. [STOC 2023] gave a solution withstretch $3+\varepsilon$, query time $O(n^{\alpha})$ but space$O(n^{2-\frac{\alpha}{f+1}})$, approaching the quadratic barrier for largesensitivity. In the realm of subquadratic space, our $f$-DSOs are the firstones that guarantee, at the same time, large sensitivity, low stretch, andnon-trivial query time. To obtain our results, we use the approximate distanceoracles of Thorup and Zwick [JACM 2005], and the derandomization of the $f$-DSOof Weimann and Yuster [TALG 2013], that was recently given by Karthik andParter [SODA 2021].

Compact Distance Oracles with Large Sensitivity and Low Stretch