论文标题
pptimal Dual Dual顶点故障连接标签
Õptimal Dual Vertex Failure Connectivity Labels
论文作者
论文摘要
在本文中，我们提出了简洁的标签方案，用于支持顶点故障下的连接查询。对于给定的$ n $ vertex Graph $ g $，$ f $ vft（分别，eft，eft）连接标签方案是一种分布式数据结构，为每个图形边缘和顶点分配一个简短标签，以给定给定标签$ u $和$ v $，以及最多$ f $ $ f $ $ $ n $ n $ ne ed $，nef $，n $ f。以$ g \ setminus f $连接。主要的复杂度度量是单个标签的长度。自从[Courcelle，Twigg，STACS '07]引入以来，FT标签方案仅是为有限的图形系列而设计的。最近的工作[Dory and Parter，PODC 2021]为边缘故障下的一般图提供了EFT标签方案，使顶点故障案例相当开放。我们为任何$ n $ vertex Graph提供第一个Sublinear $ f $ -vft标签方案。我们的关键结果是带有$ O（\ log^3 n）$位的$ 2 $ -VFT连接标签。我们的构造基于分析[Sleator和Tarjan，Stoc 1981]的众所周知的重型树分解技术的双重故障替换路径的结构。我们还为任何$ f = o（\ log \ log n）$提供了$ f $ -VFT标签（$ | v | $），这些标签是基于对现有EFT标签的减少的。
In this paper we present succinct labeling schemes for supporting connectivity queries under vertex faults. For a given $n$-vertex graph $G$, an $f$-VFT (resp., EFT) connectivity labeling scheme is a distributed data structure that assigns each of the graph edges and vertices a short label, such that 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$ are connected in $G \setminus F$. The primary complexity measure is the length of the individual labels. Since their introduction by [Courcelle, Twigg, STACS '07], FT labeling schemes have been devised only for a limited collection of graph families. A recent work [Dory and Parter, PODC 2021] provided EFT labeling schemes for general graphs under edge failures, leaving the vertex failure case fairly open. We provide the first sublinear $f$-VFT labeling schemes for $f \geq 2$ for any $n$-vertex graph. Our key result is $2$-VFT connectivity labels with $O(\log^3 n)$ bits. Our constructions are based on analyzing the structure of dual failure replacement paths on top of the well-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 EFT labels.
