Distributed verification of minimum spanning trees

DOI10.1145/1146381.1146389zbMath1314.68159OpenAlexW2077321659MaRDI QIDQ5177261

Shay Kutten, Amos Korman

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

minimum spanning treedistributed algorithmsnetwork algorithmslabeling schemesself stabilizationgraph property verificationproof labeling

Mathematics Subject Classification ID

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

Related Items (6)

Proof labeling schemes ⋮ Local MST computation with short advice ⋮ General compact labeling schemes for dynamic trees ⋮ Online computation with advice ⋮ Constructing labeling schemes through universal matrices ⋮ A new algorithm for the minimum spanning tree verification problem

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