Deterministic Fault-Tolerant Connectivity Labeling Scheme

DOI10.1145/3583668.3594584arXiv2208.11459OpenAlexW4380881539MaRDI QIDQ6202245

Taisuke Izumi, Toshimitsu Masuzawa, Tadashi Wadayama, Yuval Emek

Publication date: 26 March 2024

Published in: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2208.11459

zbMATH Keywords

graph connectivitylabeling schemefault-tolerant data structure

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(f\)-sensitivity distance oracles and routing schemes
• Subjective-cost policy routing
• \(\epsilon\)-nets and simplex range queries
• A simple proof of optimal epsilon nets
• Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
• Constrained-path labellings on graphs of bounded clique-width
• Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
• Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication
• Toward Optimal Bounds in the Congested Clique
• Connectivity oracles for failure prone graphs
• Spanners and sparsifiers in dynamic streams
• Fault-Tolerant Compact Routing Schemes for General Graphs
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Fast computation of small cuts via cycle space sampling
• Near-optimal fully-dynamic graph connectivity
• Efficient Oracles and Routing Schemes for Replacement Paths
• Faster Replacement Paths and Distance Sensitivity Oracles
• Connectivity Oracles for Graphs Subject to Vertex Failures
• Compact Forbidden-Set Routing
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• Implicat Representation of Graphs
• Compact and Fast Sensitivity Oracles for Single-Source Distances
• Derandomization in Computational Geometry
• Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension
• A nearly optimal oracle for avoiding failed vertices and edges
• MST in Log-Star Rounds of Congested Clique
• Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Logarithmic Lower Bounds in the Cell-Probe Model
• Dynamic graph connectivity in polylogarithmic worst case time
• Faster Deterministic Fully-Dynamic Graph Connectivity
• Fault-tolerant distance labeling for planar graphs

This page was built for publication: Deterministic Fault-Tolerant Connectivity Labeling Scheme