Distributed verification of minimum spanning trees

DOI10.1007/S00446-007-0025-1zbMath1266.68217OpenAlexW2023425290MaRDI QIDQ1954247

Shay Kutten, Amos Korman

Publication date: 20 June 2013

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-007-0025-1

zbMATH Keywords

minimum spanning treenetwork algorithmslabeling schemesself stabilizationgraph property verificationproof labeling schemes

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (20)

An inverse-Ackermann type lower bound for online minimum spanning tree verification ⋮ The ANTS problem ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ Proof-labeling schemes: broadcast, unicast and in between ⋮ Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs ⋮ Lower bound for constant-size local certification ⋮ Unnamed Item ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ A hierarchy of local decision ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Randomized proof-labeling schemes ⋮ Randomized distributed decision ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Redundancy in distributed proofs ⋮ Approximate proof-labeling schemes ⋮ A note on models for graph representations ⋮ A note on labeling schemes for graph connectivity ⋮ Local mending ⋮ Introduction to local certification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal EREW PRAM algorithm for minimum spanning tree verification
• Linear verification for spanning trees
• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• A simpler minimum spanning tree verification algorithm
• The local detection paradigm and its applications to self-stabilization
• Memory requirements for silent stabilization
• Optimal parallel verification of minimum spanning trees in logarithmic time
• Crash failures can drive protocols to arbitrary states
• Applications of Path Compression on Balanced Trees
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• Implicat Representation of Graphs
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• A randomized linear-time algorithm to find minimum spanning trees
• Distributed reset
• A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
• What Can be Computed Locally?
• Proof labeling schemes
• The complexity of crash failures
• What cannot be computed locally!
• Constant-time distributed dominating set approximation

This page was built for publication: Distributed verification of minimum spanning trees