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 this paper we present succinct labeling schemes for supportingconnectivity queries under vertex faults. For a given $n$-vertex graph $G$, an$f$-VFT (resp., EFT) connectivity labeling scheme is a distributed datastructure that assigns each of the graph edges and vertices a short label, suchthat given the labels of a vertex pair $u$ and $v$, and the labels of at most$f$ failing vertices (resp., edges) $F$, one can determine if $u$ and $v$ areconnected in $G \setminus F$. The primary complexity measure is the length ofthe individual labels. Since their introduction by [Courcelle, Twigg, STACS'07], FT labeling schemes have been devised only for a limited collection ofgraph families. A recent work [Dory and Parter, PODC 2021] provided EFTlabeling schemes for general graphs under edge failures, leaving the vertexfailure case fairly open. We provide the first sublinear $f$-VFT labelingschemes for $f \geq 2$ for any $n$-vertex graph. Our key result is $2$-VFTconnectivity labels with $O(\log^3 n)$ bits. Our constructions are based onanalyzing the structure of dual failure replacement paths on top of thewell-known heavy-light tree decomposition technique of [Sleator and Tarjan,STOC 1981]. We also provide $f$-VFT labels with sub-linear length (in $|V|$)for any $f=o(\log\log n)$, that are based on a reduction to the existing EFTlabels.

\~{O}ptimal Dual Vertex Failure Connectivity Labels