Brief Announcement: On Connectivity in the Broadcast Congested Clique
Tomasz Jurdziński, Krzysztof Nowicki · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2017
Recently, very fast deterministic and randomized algorithms have been obtained for connectivity and minimum spanning tree in the unicast congested clique. In contrast, no solution faster than a simple parallel implementation of the Boruvka's algorithm has been known for both problems in the broadcast congested clique. In this announcement, we present the first sub-logarithmic deterministic algorithm for connected components in the broadcast congested clique.