Title :
A near-tight lower bound on the time complexity of distributed MST construction
Author :
Peleg, David ; Rubinovich, Vitaly
Author_Institution :
Dept. of Appl. Math. & Comput. Sci., Weizmann Inst. of Sci., Rehovot, Israel
Abstract :
This paper presents a lower bound of Ω¯(D+√n) on the time required for the distributed construction of a minimum-weight spanning tree (MST) in n-vertex networks of diameter D=Ω(log n), in the bounded message model. This establishes the asymptotic near-optimality of existing time-efficient distributed algorithms for the problem, whose complexity is O(D+√nlog* n)
Keywords :
communication complexity; computational geometry; distributed algorithms; trees (mathematics); bounded message model; distributed MST construction; distributed construction; mailing problem; message-optimal algorithm; minimum-weight spanning tree; near-tight lower bound; time complexity; time-efficient distributed algorithms; Art; Broadcasting; Computer networks; Computer science; Distributed algorithms; Gallium nitride; Mathematics; Network topology; Nominations and elections;
Conference_Titel :
Foundations of Computer Science, 1999. 40th Annual Symposium on
Conference_Location :
New York City, NY
Print_ISBN :
0-7695-0409-4
DOI :
10.1109/SFFCS.1999.814597
