Distributed algorithms for random graphs

In this article we study statistical properties of a commonly used network model - an Erdős-Rényi random graph G(n,p). We are interested in the performance of distributed algorithms on large networks, which might be represented by G(n,p). We concentrate on classical problems from the field of distributed algorithms such as: finding a maximal independent set, a vertex colouring, an approximation of a minimum dominating set, a maximal matching, an edge colouring and an approximation of a maximum matching. We propose new algorithms, which with probability close to one as n→∞ construct anticipated structures in G(n,p) in a low number of rounds. Moreover, in some cases, we modify known algorithms to obtain better efficiency on G(n,p).