2018/04/07 by Heydari, Hasan, Taheri, S. Mahmoud, Kavousi, Kaveh
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1804.02513
The problem of distributed maximal independent set (MIS) is investigated on inhomogeneous random graphs with power-law weights by which the scale-free networks can be produced. Such a particular problem has been solved on graphs with n vertices by state-of-the-art algorithms with the time complexity of O(logn). We prove that for a scale-free network with power-law exponent β> 3, the induced subgraph is constructed by vertices with degrees larger than lognlog*n is a scale-free network with β' = 2, almost surely (a.s.). Then, we propose a new algorithm that computes an MIS on scale-free networks with the time complexity of O(\fraclognloglogn) a.s., which is better than O(logn). Furthermore, we prove that on scale-free networks with β≥ 3, the arboricity and degeneracy are less than 2^log1/3n with high probability (w.h.p.). Finally, we prove that the time complexity of finding an MIS on scale-free networks with β≥ 3 is O(log2/3n) w.h.p.