Tight bounds for distributed minimum-weight spanning tree verification

DOI10.1007/s00224-013-9479-7zbMath1286.68317arXiv1512.04832OpenAlexW2006444174MaRDI QIDQ372968

Amos Korman, Liah Kor, David Peleg

Publication date: 21 October 2013

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

distributed algorithmsdistributed verificationlabeling schemesminimum-weight spanning tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (8)

Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Randomized distributed decision ⋮ Unnamed Item ⋮ Message lower bounds via efficient network synchronization ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Unnamed Item ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time

Cites Work

• Unnamed Item
• An optimal EREW PRAM algorithm for minimum spanning tree verification
• Sublinear bounds for randomized leader election
• Linear verification for spanning trees
• A simpler minimum spanning tree verification algorithm
• The local detection paradigm and its applications to self-stabilization
• Memory requirements for silent stabilization
• Eigenvalues of the natural random walk on the Burnside group \(B(3,n)\)
• Distributed verification of minimum spanning trees
• Randomized distributed decision
• Optimal parallel verification of minimum spanning trees in logarithmic time
• Proof labeling schemes
• A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
• A tight unconditional lower bound on distributed randomwalk computation
• Applications of Path Compression on Balanced Trees
• An optimal minimum spanning tree algorithm
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
• A trade-off between information and communication in broadcast protocols
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• A randomized linear-time algorithm to find minimum spanning trees
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Labeling Schemes for Flow and Connectivity
• On the History of the Minimum Spanning Tree Problem
• Communication Complexity
• Distributed verification and hardness of distributed approximation
• Local Distributed Decision
• Distributed MST for constant diameter graphs

This page was built for publication: Tight bounds for distributed minimum-weight spanning tree verification