A sublinear time distributed algorithm for minimum-weight spanning trees

A sublinear time distributed algorithm for minimum-weight spanning trees

0.00 Avg rating0 Votes
Article ID: iaor19981900
Country: United States
Volume: 27
Issue: 1
Start Page Number: 302
End Page Number: 316
Publication Date: Feb 1998
Journal: SIAM Journal On Computing
Authors: , ,
Abstract:

This paper considers the question of identifying the parameters governing the behavior of fundamental global network problems. Many papers on distributed network algorithms consider the task of optimizing the running time successful when an O(n) bound is achieved on an n-vertex network. We propose that a more sensitive parameter is the network's diameter Diam. This is demonstrated in the paper by providing a distributed minimum-weight spanning tree algorithm whose time complexity is sublinear in n, but linear in Diam (specifically, O(Diam + nϵ · log* n) for ϵ = (ln 3)/(ln 6) = 0.6131...). Our result is achieved through the application of graph decomposition and edge-elimination-by-pipelining techniques that may be of independent interest.

Reviews

Required fields are marked *. Your email address will not be published.