Volume 17, Number 2, 151-170, DOI: 10.1007/s00446-004-0107-2

A linear-time optimal-message distributed algorithm for minimum spanning trees

Michalis Faloutsos and Mart Molle

View Related Documents

Abstract

In an earlier paper, Awerbuch presented an innovative distributed algorithm for solving minimum spanning tree (MST) problems that achieved optimal time and message complexity through the introduction of several advanced features. In this paper, we show that there are some cases where his algorithm can create cycles or fail to achieve optimal time complexity. We then show how to modify the algorithm to avoid these problems, and demonstrate both the correctness and optimality of the revised algorithm.
Received: 9 February 2003, Accepted: 2 April 2004, Published online: 20 July 2004
Mart Molle: This material is based upon work supported by the National Science Foundation under CAREER Grant No. 9985195, and Nortel Networks and UC CoRe fund C99-14.

Fulltext Preview

Image of the first page of the fulltext document