摘要 : In this article we study statistical properties of a commonly used network model - an Erdos-Renyi random graph G(n, p). We are interested in the performance of distributed algorithms on large networks, which might be represented b... 展开 In this article we study statistical properties of a commonly used network model - an Erdos-Renyi 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 -> infinity 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). (C) 2015 Elsevier B.V. All rights reserved. 收起