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 study a new and stronger notion of fault-tolerant graph structures whosesize bounds depend on the degree of the failing edge set, rather than the totalnumber of faults. For a subset of faulty edges $F \subseteq G$, thefaulty-degree $\deg(F)$ is the largest number of faults in $F$ incident to anygiven vertex. We design new fault-tolerant structures with size comparable toprevious constructions, but which tolerate every fault set of smallfaulty-degree $\deg(F)$, rather than only fault sets of small size $|F|$. Ourmain results are:  - New FT-Certificates: For every $n$-vertex graph $G$ and degree threshold$f$, one can compute a connectivity certificate $H \subseteq G$ with $|E(H)| =\widetilde{O}(fn)$ edges that has the following guarantee: for any edge set $F$with faulty-degree $\deg(F)\leq f$ and every vertex pair $u,v$, it holds that$u$ and $v$ are connected in $H \setminus F$ iff they are connected in $G\setminus F$. This bound on $|E(H)|$ is nearly tight. Since our certificateshandle some fault sets of size up to $|F|=O(fn)$, prior work did not imply anynontrivial upper bound for this problem, even when $f=1$.  - New FT-Spanners: We show that every $n$-vertex graph $G$ admits a$(2k-1)$-spanner $H$ with $|E(H)| = O_k(f^{1-1/k} n^{1+1/k})$ edges, whichtolerates any fault set $F$ of faulty-degree at most $f$. This bound on$|E(H)|$ optimal up to its hidden dependence on $k$, and it is close to thebound of $O_k(|F|^{1/2} n^{1+1/k} + |F|n)$ that is known for the case where thetotal number of faults is $|F|$ [Bodwin, Dinitz, Robelle SODA '22]. Our proofof this theorem is non-constructive, but by following a proof strategy ofDinitz and Robelle [PODC '20], we show that the runtime can be made polynomialby paying an additional $\text{polylog } n$ factor in spanner size.

Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free