 Home
 Search Results
 Page 1 of 1
Search for: All records

Total Resources2
 Resource Type

20
 Availability

20
 Author / Contributor
 Filter by Author / Creator


Chatterjee, Soumyottam (2)

Pandurangan, Gopal (2)

Pham, Nguyen Dinh (2)

Fathi, Reza (1)

#Tyler Phillips, Kenneth E. (0)

& Ahmed, Khadija. (0)

& AkcilOkan, O. (0)

& Akuom, D. (0)

& Aleven, V. (0)

& AndrewsLarson, C. (0)

& Archibald, J. (0)

& Attari, S. Z. (0)

& Ayala, O. (0)

& Babbitt, W. (0)

& Baek, Y. (0)

& Bahabry, Ahmed. (0)

& Bai, F. (0)

& Balasubramanian, R. (0)

& BarthCohen, L. (0)

& Bassett, L. (0)

 Filter by Editor


& Spizer, S. M. (0)

& . Spizer, S. (0)

& Ahn, J. (0)

& Bateiha, S. (0)

& Bosch, N. (0)

& Chen, B. (0)

& Chen, Bodong (0)

& Drown, S. (0)

& Higgins, A. (0)

& Kali, Y. (0)

& RuizArias, P.M. (0)

& S. Spitzer (0)

& Spitzer, S. (0)

& Spitzer, S.M. (0)

:Chaosong Huang, Gang Lu (0)

A. Beygelzimer (0)

A. E. Lischka, E.B. Dyer (0)

A. Ghate, K. Krishnaiyer (0)

A. Higgins (0)

A. I. Sacristán, J. C. (0)


Have feedback or suggestions for a way to improve these results?
!
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

We study smoothed analysis of distributed graph algorithms, focusing on the fundamental minimum spanning tree (MST) problem. With the goal of studying the time complexity of distributed MST as a function of the "perturbation" of the input graph, we posit a smoothing model that is parameterized by a smoothing parameter 0 ≤ ϵ(n) ≤ 1 which controls the amount of random edges that can be added to an input graph G per round. Informally, ϵ(n) is the probability (typically a small function of n, e.g., n¼) that a random edge can be added to a node per round. The added random edges, once they are added, can be used (only) for communication. We show upper and lower bounds on the time complexity of distributed MST in the above smoothing model. We present a distributed algorithm that, with high probability, 1 computes an MST and runs in Õ(min{1/√ϵ(n)2O(√log n), D+ √n}) rounds2 where ϵ is the smoothing parameter, D is the network diameter and n is the network size. To complement our upper bound, we also show a lower bound of Ω(min{1/√ϵ(n), D + √n}). We note that the upper and lower bounds essentially match except for a multiplicative 2O(√log n)more »

Chatterjee, Soumyottam ; Fathi, Reza ; Pandurangan, Gopal ; Pham, Nguyen Dinh ( , 38th IEEE International Conference on Distributed Computing Systems (ICDCS))