期刊名称：Journal of Theoretical and Applied Information Technology
印刷版ISSN：1992-8645
电子版ISSN：1817-3195
出版年度：2014
卷号：67
期号：3
出版社：Journal of Theoretical and Applied
摘要：In this paper we introduce and analyze a probabilistic distributed algorithm for minimum spanning tree construction. Our algorithm is based firstly on the handshake algorithm that produces firstly k sub-spanning trees, where k is the size of the maximal matching produced. Secondly, the merged step of our algorithm is executed in a distributed manner and following some roles to reduce the total number of those sub-spanning from k to 1. We proof that the residual graph is acyclic and all vertices belong to it. A detailed analysis of the number of exchanged messages is carried on to validate the effectiveness of our algorithm.
