Fetching the paper…

Reading the bibliography…

2016

Deterministic MST Sparsification in the Congested Clique

Korhonen, Janne H.

Original
PDF
Post on X

Understand

We give a simple deterministic constant-round algorithm in the congested clique model for reducing the number of edges in a graph to $n^{1+\varepsilon}$ while preserving the minimum spanning forest, where $\varepsilon > 0$ is any constant.

This implies that in the congested clique model, it is sufficient to improve MST and other connectivity algorithms on graphs with slightly superlinear number of edges to obtain a general improvement.
As a byproduct, we also obtain a simple alternative proof showing that MST can be computed deterministically in $O(\log \log n)$ rounds.

Deterministic MST Sparsification in the Congested Clique · Around

Built on

A randomized linear-time algorithm to find minimum spanning trees
David R. Karger, Philip N. Klein, and Robert E. Tarjan · 1995
Earlier work this paper cites.
Minimum-weight spanning tree construction in O ⁡ ( log ⁡ log ⁡ n ) O(\log\log n) communication rounds
Original
Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg · 2005
Earlier work this paper cites.

Similar

Optimal deterministic routing and sorting on the congested clique
Christoph Lenzen · 2013
Cited alongside, same era.
Toward optimal bounds in the congested clique: Graph connectivity and MST
James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato · 2015
Cited alongside, same era.

Then

MST in log-star rounds of congested clique
Mohsen Ghaffari and Merav Parter · 2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…