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

In a graph $G$ with a source $s$, we design a distance oracle that can answerthe following query: Query$(s,t,e)$ -- find the length of shortest path from afixed source $s$ to any destination vertex $t$ while avoiding any edge $e$. Wedesign a deterministic algorithm that builds such an oracle in$\tilde{O}(m\sqrt n)$ time. Our oracle uses $\tilde{O}(n\sqrt n)$ space and cananswer queries in $\tilde{O}(1)$ time. Our oracle is an improvement of the workof Bil\`{o} et al. (ESA 2021) in the preprocessing time, which constructs thefirst deterministic oracle for this problem in $\tilde{O}(m\sqrt n+n^2)$ time.  Using our distance oracle, we also solve the {\em single source replacementpath problem} (SSR problem). Chechik and Cohen (SODA 2019) designed arandomized combinatorial algorithm to solve the SSR problem. The running timeof their algorithm is $\tilde{O}(m\sqrt n + n^2)$. In this paper, we show thatthe SSR problem can be solved in $\tilde{O}(m\sqrt n + |\mathcal{R}|)$ time,where $\mathcal{R}$ is the output set of the SSR problem in $G$. Our SSRalgorithm is optimal (upto polylogarithmic factor) as there is a conditionallower bound of $\Omega(m\sqrt n)$ for any combinatorial algorithm that solvesthis problem.

Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path problem