ABSTRACT
This paper studies the problem of constructing a minimum-weight spanning tree (MST) in a distributed network. This is one of the most important problems in the area of distributed computing. There is a long line of gradually improving protocols for this problem, and the state of the art today is a protocol with running time O(∧(G) + √n log* n) due to Kutten and Peleg [KP95], where ∧(G) denotes the diameter of the graph G. Peleg and Rubinovich [PR99] have shown that (√n) time is required for constructing MST even on graphs of small diameter, and claimed that their result "establishes the asymptotic near-optimality" of the protocol of [KP95].In this paper we refine this claim, and devise a protocol that constructs the MST in Õ(μ(G = w + √n) rounds, where μ(G,μ) is the MST-radius of the graph. The ratio between the diameter and the MST-radius may be as large as Θ(n), and, consequently, on some inputs our protocol is faster than the protocol of [KP95] by a factor of (√n). Also, on every input, the running time of our protocol is never greater than twice the running time of the protocol of [KP95].As part of our protocol for constructing an MST, we develop a protocol for constructing neighborhood covers with a drastically improved running time. The latter result may be of independent interest.
Recommendations
A faster distributed protocol for constructing a minimum spanning tree
This paper studies the problem of constructing a minimum-weight spanning tree (MST) in a distributed network. This is one of the most important problems in the area of distributed computing. There is a long line of gradually improving protocols for this ...
A highly asynchronous minimum spanning tree protocol
In this paper, we present an efficient distributed protocol for constructing a minimum-weight spanning tree (MST). Gallager, Humblet and Spira [5] proposed a protocol for this problem with time and message complexities O(N log N) and O(E + N log N) ...
The expected complexity of Prim's minimum spanning tree algorithm
We study the expected performance of Prim's minimum spanning tree (MST) algorithm implemented using ordinary heaps. We show that this implementation runs in linear or almost linear expected time on a wide range of graphs. This helps to explain why Prim'...
Comments