EUVIMEDEUVIMED entdecken
Crossref

Fault-Tolerant Labeling and Compact Routing Schemes

Michal Dory, Merav Parter

SIAM Journal on Computing · 31.08.2026 · 55 (4) · 671-707

DOI: 10.1137/25m1722494 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 04.08.2026. Verfasst von Michal Dory und 1 weiteren Autor:innen. Die Arbeit nennt 46 Literaturangaben. Gefördert von: Israel Science Foundation, Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung, European Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The paper presents fault-tolerant (FT) labeling schemes for general graphs, as well as improved FT routing schemes. For a given [Formula: see text]-vertex graph [Formula: see text] and a bound [Formula: see text] on the number of faults, an [Formula: see text]-FT connectivity labeling scheme is a distributed data structure that assigns to each of the graph edges and vertices a short label, such that given the labels of a vertex pair [Formula: see text] and [Formula: see text], and the labels of at most [Formula: see text] failing edges [Formula: see text], one can determine if [Formula: see text] and [Formula: see text] are connected in [Formula: see text]. The primary complexity measure is the length of the individual labels. Since their introduction by [Courcelle, Twigg, STACS ’07], compact FT labeling schemes have been devised only for a limited collection of graph families. In this work, we fill in this gap by proposing two (independent) FT connectivity labeling schemes for general graphs, with a nearly optimal label length. This serves the basis for providing also FT approximate distance labeling schemes, and ultimately also routing schemes. Our main results for an [Formula: see text]-vertex graph and a fault bound [Formula: see text] are (1) There is a randomized FT connectivity labeling scheme with a label length of [Formula: see text] bits, hence optimal for [Formula: see text]. This scheme is based on the notion of cycle space sampling [Pritchard, Thurimella, TALG ’11]. (2) There is a randomized FT connectivity labeling scheme with a label length of [Formula: see text] bits (independent of the number of faults [Formula: see text]). This scheme is based on the notion of linear sketches of [Ahn et al., SODA ’12]. (3) For a given stretch parameter [Formula: see text], there is a randomized routing scheme that routes a message from [Formula: see text] to [Formula: see text] in the presence of a set [Formula: see text] of faulty edges (unknown to [Formula: see text]) over a path of length [Formula: see text]. The routing labels have [Formula: see text] bits, the header size is [Formula: see text] bits, and each routing table has only [Formula: see text] bits. (Throughout the paper, we use the notation [Formula: see text] to hide poly-logarithmic in [Formula: see text] terms.) The results also hold for weighted graphs with positive polynomial weights. This significantly improves over the state-of-the-art bounds by [Chechik, ICALP ’11], providing the first scheme with sublinear FT labeling and routing schemes for general graphs.

Förderung

  • Israel Science Foundation
  • Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
  • European Research Council

Zitieren

APA

Dory, M., & Parter, M. (2026). Fault-Tolerant Labeling and Compact Routing Schemes. SIAM Journal on Computing, 55(4), 671-707. https://doi.org/10.1137/25m1722494

Vancouver

Dory M, Parter M. Fault-Tolerant Labeling and Compact Routing Schemes. SIAM Journal on Computing. 2026;55(4):671-707. doi:10.1137/25m1722494

BibTeX
@article{Dory2026,
  author = {Dory, Michal and Parter, Merav},
  title = {Fault-Tolerant Labeling and Compact Routing Schemes},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {4},
  pages = {671--707},
  doi = {10.1137/25m1722494}
}
Kostenlos starten →