An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
Mark Goldberg, Thomas H. Spencer · SIAM Journal on Discrete Mathematics · 1993
Every graph with n vertices and m edges has an independent set containing at least $n^2 / (2m + n)$ vertices. This paper presents a parallel algorithm that finds an independent set of this size and runs in $O( \log^3 n )$ time on a CROW PRAM with $O( ( m + n)\alpha ( m,n )/ \log^2 n)$ processors, where $\alpha ( n,m )$ is a functional inverse of Ackerman’s function. The ideas used in the design of this algorithm are also used to design an algorithm that, with the same resources, finds a vertex coloring satisfying certain minimality conditions.