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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

For an input graph $G=(V, E)$ and a source vertex $s \in V$, the\emph{$\alpha$-approximate vertex fault-tolerant distance sensitivity oracle}(\emph{$\alpha$-VSDO}) answers an $\alpha$-approximate distance from $s$ to $t$in $G-x$ for any query $(x, t)$. It is a data structure version of theso-called single-source replacement path problem (SSRP). In this paper, wepresent a new \emph{nearly linear time} algorithm of constructing the $(1 +\epsilon)$-VSDO for any weighted directed graph of $n$ vertices and $m$ edgeswith integer weights in range $[1, W]$, and any positive constant $\epsilon \in(0, 1]$. More precisely, the presented oracle attains $\tilde{O}(m / \epsilon +n /\epsilon^2)$ construction time, $\tilde{O}(n/ \epsilon)$ size, and$\tilde{O}(1/\epsilon)$ query time for any polynomially-bounded $W$. To thebest of our knowledge, this is the first non-trivial result for SSRP/VSDObeating the trivial $\tilde{O}(mn)$ computation time for directed graphs withpolynomially-bounded edge weights. Such a result has been unknown so far evenfor the setting of $(1 + \epsilon)$-approximation. It also implies that theknown barrier of $\Omega(m\sqrt{n})$ time for the exact SSRP by Chechik andMagen~[ICALP2020] does not apply to the case of approximation.

Constructing Approximate Single-Source Distance Sensitivity Oracles in Nearly Linear Time