  The {Congested Clique} is a distributed-computing model for single-hop
networks with restricted bandwidth that has been very intensively studied
recently. It models a network by an $n$-vertex graph in which any pair of
vertices can communicate one with another by transmitting $O(\log n )$ bits in
each round. Various problems have been studied in this setting, but for some of
them the best-known results are those for general networks. In this paper we
devise significantly improved algorithms for various symmetry-breaking
problems, such as forests-decompositions, vertex-colorings, and maximal
independent set.
  We analyze the running time of our algorithms as a function of the arboricity
$a$ of a clique subgraph that is given as input. Our algorithms are especially
efficient in Trees, planar graphs, graphs with constant genus, and many other
graphs that have bounded arboricity, but unbounded size. We obtain
$O(a)$-forest-decomposition algorithm with $O(\log a)$ time that improves the
previously-known $O(\log n)$ time, $O(a^{2 + \epsilon})$-coloring in $O(\log^*
n)$ time that improves upon an $O(\log n)$-time algorithm, $O(a)$-coloring in
$O(a^{\epsilon})$-time that improves upon several previous algorithms, and a
maximal independent set algorithm with $O(\sqrt a)$ time that improves at least
quadratically upon the state-of-the-art for small and moderate values of $a$.
  Those results are achieved using several techniques. First, we produce a
forest decomposition with a helpful structure called {$H$-partition} within
$O(\log a)$ rounds. In general graphs this structure requires $\Theta(\log n)$
time, but in Congested Cliques we are able to compute it faster. We employ this
structure in conjunction with partitioning techniques that allow us to solve
various symmetry-breaking problems efficiently.

Distributed, Parallel, and Cluster Computing;Data Structures and Algorithms