Distributed verification of minimum spanning trees

DOI10.1145/1146381.1146389MaRDI QIDQ5177261zbMATH OpenOpenAlexFDO

Authors Amos Korman, Shay Kutten

Publication date 10 March 2015

Published in Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1146381.1146389

zbMATH Keywords

distributed algorithmsgraph property verificationlabeling schemesminimum spanning treenetwork algorithmsproof labelingself stabilization

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Distributed verification of minimum spanning trees
• Distributed verification and hardness of distributed approximation

Cited in

(10)

• General compact labeling schemes for dynamic trees
• Distributed verification of minimum spanning trees
• A new algorithm for the minimum spanning tree verification problem
• Proof labeling schemes
• scientific article; zbMATH DE number 1264417 (Why is no real title available?)
• Online computation with advice
• Proving Distributed Algorithms for Mobile Agents: Examples of Spanning Tree Computation in Anonymous Networks
• Randomized Lower Bound for Distributed Spanning-Tree Verification
• Local MST computation with short advice
• Constructing labeling schemes through universal matrices

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5177261)