Tight bounds on the message complexity of distributed tree verification
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 2123255 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- A Near-Optimal Deterministic Distributed Synchronizer
- A brief account of runtime verification
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- A simple deterministic distributed MST algorithm with near-optimal time and message complexities
- A simpler minimum spanning tree verification algorithm
- A time- and message-optimal distributed algorithm for minimum spanning trees
- A trade-off between information and communication in broadcast protocols
- An optimal EREW PRAM algorithm for minimum spanning tree verification
- Applications of Path Compression on Balanced Trees
- Can We Break Symmetry with o(m) Communication?
- Construction and impromptu repair of an MST in a distributed network with o(m) communication
- Distributed Computing: A Locality-Sensitive Approach
- Distributed MST and broadcast with fewer messages, and faster gossiping
- Distributed approximation algorithms for weighted shortest paths
- Distributed verification and hardness of distributed approximation
- Distributed verification of minimum spanning trees
- Electing a leader in a synchronous ring
- Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
- Fast routing table construction using small messages (extended abstract)
- Fault-tolerant approximate BFS structures
- Graph spanners
- Minimal Regular Graphs of Girths Eight and Twelve
- On the Complexity of Universal Leader Election
- Proof labeling schemes
- Self-stabilizing extensions for message-passing systems
- Survey of distributed decision
- Symmetry breaking in the Congest model: time- and message-efficient algorithms for ruling sets
- The power of distributed verifiers in interactive proofs
- Tight bounds for distributed minimum-weight spanning tree verification
- Time-message trade-offs in distributed algorithms
- Towards a complexity theory for local distributed computing
- Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
This page was built for publication: Tight bounds on the message complexity of distributed tree verification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6954066)
