Distributed algorithms for random graphs

作者：Krzywdzinski K; Rybarczyk K^*

来源：Theoretical Computer Science, 2015, 605: 95-105.

DOI：10.1016/j.tcs.2015.08.037

• Distributed algorithms
• Random graphs
• Colouring
• Independent set
• Dominating set
• Matching

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).

• 出版日期2015-11-9