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

We (nearly) settle the time complexity for computing vertex fault-tolerant(VFT) spanners with optimal sparsity (up to polylogarithmic factors). VFTspanners are sparse subgraphs that preserve distance information, up to a smallmultiplicative stretch, in the presence of vertex failures. These structureswere introduced by [Chechik et al., STOC 2009] and have received a lot ofattention since then. We provide algorithms for computing nearly optimal$f$-VFT spanners for any $n$-vertex $m$-edge graph, with near optimal runningtime in several computational models:  - A randomized sequential algorithm with a runtime of $\widetilde{O}(m)$(i.e., independent in the number of faults $f$). The state-of-the-art timebound is $\widetilde{O}(f^{1-1/k}\cdot n^{2+1/k}+f^2 m)$ by [Bodwin, Dinitz andRobelle, SODA 2021].  - A distributed congest algorithm of $\widetilde{O}(1)$ rounds. Improvingupon [Dinitz and Robelle, PODC 2020] that obtained FT spanners withnear-optimal sparsity in $\widetilde{O}(f^{2})$ rounds.  - A PRAM (CRCW) algorithm with $\widetilde{O}(m)$ work and $\widetilde{O}(1)$depth. Prior bounds implied by [Dinitz and Krauthgamer, PODC 2011] obtainedsub-optimal FT spanners using $\widetilde{O}(f^3m)$ work and$\widetilde{O}(f^3)$ depth.  An immediate corollary provides the first nearly-optimal PRAM algorithm forcomputing nearly optimal $\lambda$-\emph{vertex} connectivity certificatesusing polylogarithmic depth and near-linear work. This improves thestate-of-the-art parallel bounds of $\widetilde{O}(1)$ depth and $O(\lambda m)$work, by [Karger and Motwani, STOC'93].

\~{O}ptimal Vertex Fault-Tolerant Spanners in \~{O}ptimal Time: Sequential, Distributed and Parallel