Distributed maximal independent set on inhomogeneous random graphs
Hasan Heydari, Seyed Mahmoud Taheri · 2017
A maximal independent set (MIS) on a graph is an inclusion-maximal set of mutually non-adjacent nodes. The problem of computing an MIS is one of the fundamental problems in the area of parallel and distributed algorithms. In this paper, we investigate the distributed maximal independent set problem on inhomogeneous random graphs by which the scale-free networks can be produced. Such a particular problem has been solved by state-of-the-art algorithms with time complexity of O(log n). We prove that on inhomogeneous random graphs with n nodes and power law exponent β ≥ 3, the arboricity and the degeneracy is less than 2(log n)1/3with high probability (w.h.p.). Thus, the time complexity of finding an MIS on these graphs is O(log2/3n). Furthermore, we propose a new algorithm for computing an MIS on inhomogeneous random graphs with power law exponent β2/3n) for β <; 3, which is better than O(log n).