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

broadcastcongested cliqueconnected componentsminimum spanning treerandomized algorithmsunicast

Mathematics Subject Classification ID

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

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

(42)

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

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)