MST in Log-Star Rounds of Congested Clique

DOI10.1145/2933057.2933103zbMath1376.68109MaRDI QIDQ5361911

Mohsen Ghaffari, Merav Parter

Publication date: 29 September 2017

Published in: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2933057.2933103

zbMATH Keywords

connectivity; congested clique; linear sketching

Mathematics Subject Classification ID

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C40: Connectivity

68W20: Randomized algorithms

68W15: Distributed algorithms

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE, Fault-tolerant graph realizations in the congested clique, Exact distributed sampling, Distributed PageRank computation with improved round complexities, Brief Announcement: What Can We Compute in a Single Round of the Congested Clique?, Deterministic Fault-Tolerant Connectivity Labeling Scheme, Fast approximate shortest paths in the congested clique, Near-optimal scheduling in the congested clique, Approximate minimum directed spanning trees under congestion, Graph reconstruction in the congested clique, Derandomizing local distributed algorithms under bandwidth restrictions, A distributed algorithm for directed minimum-weight spanning tree, Sparsifying Congested Cliques and Core-Periphery Networks