DocumentCode
3450182
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
fYear
1999
fDate
1999
Firstpage
253
Lastpage
261
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1999. 40th Annual Symposium on
Conference_Location
New York City, NY
ISSN
0272-5428
Print_ISBN
0-7695-0409-4
Type
conf
DOI
10.1109/SFFCS.1999.814597
Filename
814597
Link To Document