MST in O(1) rounds of congested clique

MaRDI QIDQ4608063zbMATH OpenFDO

Authors Tomasz Jurdziński, Krzysztof Nowicki

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1707.08484, http://dl.acm.org/citation.cfm?id=3175472

zbMATH Keywords

minimum spanning treerandomized algorithmsbroadcastconnected componentsunicastcongested clique

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)

Recommendations

• MST in log-star rounds of congested clique
• Super-fast MST algorithms in the congested clique using \(o(m)\) messages
• Toward optimal bounds in the congested clique, graph connectivity and MST
• On range and edge capacity in the congested clique
• Connectivity and minimum cut approximation in the broadcast congested clique

Cited in

(34)

• Toward optimal bounds in the congested clique, graph connectivity and MST
• Fault-tolerant graph realizations in the congested clique
• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• Congested Clique Algorithms for the Minimum Cut Problem
• Brief announcement: Deterministic graph connectivity in the broadcast congested clique
• scientific article; zbMATH DE number 7561635 (Why is no real title available?)
• Low-congestion shortcut and graph parameters
• Approximate minimum directed spanning trees under congestion
• Near-optimal scheduling in the congested clique
• Exact distributed sampling
• Derandomizing local distributed algorithms under bandwidth restrictions
• Large-scale distributed algorithms for facility location with outliers
• Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
• A deterministic algorithm for the MST problem in constant rounds of congested clique
• Simple distributed spanners in dense congest networks
• Sparsifying congested cliques and core-periphery networks
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Distributed PageRank computation with improved round complexities
• The impact of locality in the broadcast congested clique model
• md-MST is NP-hard for \(d\geq 3\)
• Brief Announcement: What Can We Compute in a Single Round of the Congested Clique?
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Deterministic Fault-Tolerant Connectivity Labeling Scheme
• On range and edge capacity in the congested clique
• MST in log-star rounds of congested clique
• Super-fast MST algorithms in the congested clique using \(o(m)\) messages
• Fast approximate shortest paths in the congested clique
• GHS algorithm on a graph with random weights
• Graph reconstruction in the congested clique
• Streaming Euclidean MST to a constant factor
• A distributed algorithm for directed minimum-weight spanning tree
• scientific article; zbMATH DE number 7561507 (Why is no real title available?)
• scientific article; zbMATH DE number 7525452 (Why is no real title available?)
• Distributed MST and broadcast with fewer messages, and faster gossiping

This page was built for publication: MST in \(O(1)\) rounds of congested clique

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608063)