Buchumschlag

Tight Bounds on the Message Complexity of Distributed Tree Verification

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kutten, Shay, Robinson, Peter, Tan, Ming Ming
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Distributed, Parallel, and Cluster Computing Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The Quantum Message Complexity of Distributed Wake-Up with Advice
von: Robinson, Peter, et al.
Veröffentlicht: (2026)

Deterministic Lower Bounds for $k$-Edge Connectivity in the Distributed Sketching Model
von: Robinson, Peter, et al.
Veröffentlicht: (2025)

Perfect Matching with Few Link Activations
von: Mirault, Hugo, et al.
Veröffentlicht: (2025)

Message Optimality and Message-Time Trade-offs for APSP and Beyond
von: Dufoulon, Fabien, et al.
Veröffentlicht: (2025)

The Local Information Cost of Distributed Graph Spanners
von: Robinson, Peter
Veröffentlicht: (2020)

Tight Bounds for Constant-Round Domination on Graphs of High Girth and Low Expansion
von: Lenzen, Christoph, et al.
Veröffentlicht: (2024)

A Tight Lower Bound for 3-Coloring Grids in the Online-LOCAL Model
von: Chang, Yi-Jun, et al.
Veröffentlicht: (2023)

Overlay Network Construction: Improved Overall and Node-Wise Message Complexity
von: Chang, Yi-Jun, et al.
Veröffentlicht: (2024)

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

What Can We Compute in a Single Round of the Congested Clique?
von: Robinson, Peter
Veröffentlicht: (2022)

Bounded Memory in Distributed Networks
von: Basat, Ran Ben, et al.
Veröffentlicht: (2025)

String Problems in the Congested Clique Model
von: Golan, Shay, et al.
Veröffentlicht: (2025)

Two Efficient Message-passing Exclusive Scan Algorithms
von: Träff, Jesper Larsson
Veröffentlicht: (2026)

Dynamic Maximal Matching in Clique Networks
von: Li, Minming, et al.
Veröffentlicht: (2024)

Memory Bounds for Concurrent Bounded Queues
von: Aksenov, Vitaly, et al.
Veröffentlicht: (2021)

Time-Optimal and Energy-Efficient Deterministic Consensus
von: Meir, Shachar, et al.
Veröffentlicht: (2025)

Brief Announcement: Distributed Unconstrained Local Search for Multilevel Graph Partitioning
von: Sanders, Peter, et al.
Veröffentlicht: (2024)

Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs
von: Baumecker, Malte, et al.
Veröffentlicht: (2025)

Low-Distortion Clustering in Bounded Growth Graphs
von: Chang, Yi-Jun, et al.
Veröffentlicht: (2024)

Improved Approximation Bounds for Minimum Weight Cycle in the CONGEST Model
von: Manoharan, Vignesh, et al.
Veröffentlicht: (2023)

Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model
von: Manoharan, Vignesh, et al.
Veröffentlicht: (2022)

Distributed Stochastic Graph Algorithms
von: Censor-Hillel, Keren, et al.
Veröffentlicht: (2026)

Optimal Distributed Replacement Paths
von: Chang, Yi-Jun, et al.
Veröffentlicht: (2025)

Distributed Graph Algorithms with Predictions
von: Boyar, Joan, et al.
Veröffentlicht: (2025)

Distributed Maximum Flow in Planar Graphs
von: Abd-Elhaleem, Yaseen, et al.
Veröffentlicht: (2024)

Local Density and its Distributed Approximation
von: Christiansen, Aleksander Bjørn, et al.
Veröffentlicht: (2024)

$k$-Center Clustering in Distributed Models
von: Biabani, Leyla, et al.
Veröffentlicht: (2024)

Fast Deterministic Distributed Degree Splitting
von: Maus, Yannic, et al.
Veröffentlicht: (2026)

Meta-Theorems for Cuttable Distributed Problems
von: Bonamy, Marthe, et al.
Veröffentlicht: (2026)

Distributed Subgraph Finding: Progress and Challenges
von: Censor-Hillel, Keren
Veröffentlicht: (2022)

Towards Optimal Distributed Delta Coloring
von: Jakob, Manuel, et al.
Veröffentlicht: (2025)

On Distributed Computation of the Minimum Triangle Edge Transversal
von: Censor-Hillel, Keren, et al.
Veröffentlicht: (2024)

Distributed Delta-Coloring under Bandwidth Limitations
von: Maus, Yannic, et al.
Veröffentlicht: (2024)

Fully-Distributed Byzantine Agreement in Sparse Networks
von: Augustine, John, et al.
Veröffentlicht: (2024)

Distributed Santa Claus via Global Rounding
von: de Vos, Tijn, et al.
Veröffentlicht: (2026)

Congested Clique Counting for Local Gibbs Distributions
von: Sobel, Joshua Z.
Veröffentlicht: (2025)

A Simple and Robust Protocol for Distributed Counting
von: Cohen, Edith, et al.
Veröffentlicht: (2025)

A Simple Distributed Deterministic Planar Separator
von: Abd-Elhaleem, Yaseen, et al.
Veröffentlicht: (2026)

Distributed Lovász Local Lemma under Bandwidth Limitations
von: Halldórsson, Magnús M., et al.
Veröffentlicht: (2024)

Towards Optimal Distributed Edge Coloring with Fewer Colors
von: Jakob, Manuel, et al.
Veröffentlicht: (2025)