Constructing a Maximal Independent Set in Parallel

The problem of constructing in parallel a maximal independent set of a given graph is considered. A new deterministic NC-algorithm implemented in the EREW PRAM model is presented. On graphs with n vertices and m edges, it uses O ((n +m )/logn ) processors and runs in O (log³ n ) time. This reduces by a factor of logn both the running time and the processor count of the previously fastest deterministic algorithm which solves the problem using a linear number of processors