A parallel algorithm for the independent set problem

An independent set in an undirected graph is a collection of pairwise nonadjacent vertices. Wei (1981) has shown that every graph with n vertices and degree sequence d₁, d₂, . . ., d_n has an independent set of size ω(G)=ⁿΣ_i=1(1/d_i +1´), and the well known greedy algorithm can be used to compute an independent set of this size. The current paper gives a sublinear parallel algorithm that computes an independent set of size ω(G). The algorithm uses a linear number of processors and has O((n+m)^α) time complexity under the EREW PRAM model where m is the number of edges and α>1/2 is arbitrary