arXiv preprint ·
Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
For an undirected graph $G = (V,E)$ and a fault bound $f$, an edge-fault-tolerant connectivity labeling scheme assigns short labels to vertices and edges, so that for any vertex pair $(s,t)$ and failed edge set $F\subseteq E$ with $|F|\leq f$, the connectivity between $s$ and $t$ in $G-F$ can be answered by inspecting only the labels of $s$, $t$ and edges in $F$. In this paper, we present a labeling scheme that uses $O(\log^{2}n)$-bit labels that can be computed in deterministic polynomial time. This improves upon the previous $\tilde{O}(\sqrt{f})$ deterministic bound of [Long, Pettie, Saranurak'25], and even slightly improves the $O(\min\{f+\log n,\log^{2}n\log f\})$ randomized bound of [Dory, Parter'21] and [Long, Pettie, Saranurak'25] when $f = Ω(\log^{2}n)$. Moreover, for a general $f$, this is the first labeling scheme that produces an $\tilde{O}(1)$-size labeling which is simultaneously correct across all queries. Our approach combines the cycle-space-based labeling scheme from Dory and Parter with a recent result by [Knauer'26] on sparse cycle bases.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters
Streaming Algorithms for Gaussian Kernel Density Statistics
Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian
Scalable Composition of Byzantine Agreements under Reorder Attacks
Generalized Graph Search Trees
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.