ID:14356
Type of Publication: Journal Articles
Authors: Zvi Lotker, Boaz.Patt-Shamir, Elan.Pavlov, David.Peleg
Title: Minimum-weight spanning tree construction in O(log log n) communication rounds
Name of the Journal: SIAM Journal on Computing
Year: 2006
Volume: 35
Issue: 1
Pages: 120 - 131
Abstract: We consider a simple model for overlay networks, where all n processes are connected to all other processes, and each message contains at most O(log n) bits. For this model, we present a distributed algorithm which constructs a minimum-weight spanning tree in O(log log n) communication rounds, where in each round any process can send a message to every other process. If message size is Θ(ne) for some ε > 0, then the number of communication rounds is O(log 1/ε). © 2005 Society for Industrial and Applied Mathematics.
Keywords: Mathematical models;Algorithms;Communication; ,
Last Updated: 9/4/2007 12:00:00 AM
Powered by Rami Palombo © 2005
Search in: Google Scholar  |  Scitation