Paper Info
Title
Tight Bounds for Distributed Minimum-Weight Spanning Tree Verification.
Abstract
This paper introduces the notion of distributed verification without preprocessing. It focuses on the Minimum-weight Spanning Tree (MST) verification problem and establishes tight upper and lower bounds for the time and message complexities of this problem. Specifically, we provide an MST verification algorithm that achieves messages and time, where is the number of edges in the given graph , is the number of nodes, and is ’s diameter. On the other hand, we show that any MST verification algorithm must send messages and incur time in worst case.Our upper bound result appears to indicate that the verification of an MST may be easier than its construction, since for MST construction, both lower bounds of messages and time hold, but at the moment there is no known distributed algorithm that constructs an MST and achieves messages and time. Specifically, the best known time-optimal algorithm (using time) requires (+ ) messages, and the best known message-optimal algorithm (using messages) requires () time. On the other hand, our lower bound results indicate that the verification of an MST is not significantly easier than its construction.
Year
DOI
Venue
2013
10.1007/s00224-013-9479-7
Theory of Computing Systems \/ Mathematical Systems Theory
Keywords
Field
DocType
Distributed algorithms,Distributed verification,Labeling schemes,Minimum-weight spanning tree
Discrete mathematics,Graph,Combinatorics,Upper and lower bounds,Distributed algorithm,Tilde,Spanning tree,Minimum weight,Mathematics
Journal
Volume
Issue
ISSN
abs/1512.04832
2
Theory of Computing Systems, Springer Verlag, 2013, \<10.1007/s00224-013-9479-7\>
Citations 
PageRank 
References 
8
0.46
25
Authors
3
Name
Order
Citations
PageRank
Liah Kor1863.54
Amos Korman277947.29
David Peleg36662824.19