Cover Image

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Boneh, Itai, Chechik, Shiri, Golan, Shay, Mozes, Shay, Weimann, Oren
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Distributed, Parallel, and Cluster Computing
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
by: Boneh, Itai, et al.
Published: (2025)

String Problems in the Congested Clique Model
by: Golan, Shay, et al.
Published: (2025)

Distributed Maximum Flow in Planar Graphs
by: Abd-Elhaleem, Yaseen, et al.
Published: (2024)

A Simple Distributed Deterministic Planar Separator
by: Abd-Elhaleem, Yaseen, et al.
Published: (2026)

Faster Multi-Source Reachability and Approximate Distances via Shortcuts, Hopsets and Matrix Multiplication
by: Elkin, Michael, et al.
Published: (2025)

Tight Bounds on the Message Complexity of Distributed Tree Verification
by: Kutten, Shay, et al.
Published: (2024)

Scalable Fault-Tolerant MapReduce
by: Hespe, Demian, et al.
Published: (2024)

Near-Optimal Fault Tolerance for Efficient Batch Matrix Multiplication via an Additive Combinatorics Lens
by: Censor-Hillel, Keren, et al.
Published: (2023)

A Fault-Tolerant Version of Safra's Termination Detection Algorithm
by: Fokkink, Wan, et al.
Published: (2026)

Near-Optimal Resilient Labeling Schemes
by: Censor-Hillel, Keren, et al.
Published: (2024)

Optimal Deterministic Rendezvous in Labeled Lines
by: Bourreau, Yann, et al.
Published: (2025)

Universally Optimal Information Dissemination and Shortest Paths in the HYBRID Distributed Model
by: Chang, Yi-Jun, et al.
Published: (2023)

Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
by: Bonamy, Marthe, et al.
Published: (2025)

Distances in Planar Graphs are Almost for Free!
by: Mozes, Shay, et al.
Published: (2026)

Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs
by: Gil, Yuval
Published: (2024)

Distributed Interactive Proofs for Planarity with Log-Star Communication
by: Gil, Yuval, et al.
Published: (2025)

Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs
by: Baumecker, Malte, et al.
Published: (2025)

New Distributed Interactive Proofs for Planarity: A Matter of Left and Right
by: Gil, Yuval, et al.
Published: (2025)

Hamming Distance Oracle
by: Boneh, Itai, et al.
Published: (2024)

Local Density and its Distributed Approximation
by: Christiansen, Aleksander Bjørn, et al.
Published: (2024)

All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free
by: Fischer, Orr, et al.
Published: (2025)

Massively Parallel Algorithms for Approximate Shortest Paths
by: Dory, Michal, et al.
Published: (2024)

Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes
by: Filtser, Arnold, et al.
Published: (2026)

Improved All-Pairs Approximate Shortest Paths in Congested Clique
by: Bui, Hong Duc, et al.
Published: (2024)

Improved Approximation Bounds for Minimum Weight Cycle in the CONGEST Model
by: Manoharan, Vignesh, et al.
Published: (2023)

Optimal Distributed Replacement Paths
by: Chang, Yi-Jun, et al.
Published: (2025)

A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams
by: Cambus, Mélanie, et al.
Published: (2022)

Towards Optimal Distributed Delta Coloring
by: Jakob, Manuel, et al.
Published: (2025)

Multi-Agent Online Graph Exploration on Cycles and Tadpole Graphs
by: Akker, Erik van den, et al.
Published: (2024)

Time-Optimal and Energy-Efficient Deterministic Consensus
by: Meir, Shachar, et al.
Published: (2025)

Optimal local certification on graphs of bounded pathwidth
by: Baterisna, Dan Alden, et al.
Published: (2025)

A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
by: Assadi, Sepehr
Published: (2023)

Towards Optimal Distributed Edge Coloring with Fewer Colors
by: Jakob, Manuel, et al.
Published: (2025)

Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
by: Flin, Maxime, et al.
Published: (2026)

Almost Optimal Algorithms for Token Collision in Anonymous Networks
by: Bai, Sirui, et al.
Published: (2024)

Decentralized Distributed Graph Coloring II: degree+1-Coloring Virtual Graphs
by: Flin, Maxime, et al.
Published: (2024)

Deterministic Longest Common Subsequence Approximation in Near-Linear Time
by: Boneh, Itai, et al.
Published: (2025)

The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$
by: Boneh, Itai, et al.
Published: (2025)

Message Optimality and Message-Time Trade-offs for APSP and Beyond
by: Dufoulon, Fabien, et al.
Published: (2025)

Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering
by: Dhulipala, Laxman, et al.
Published: (2024)