A New Parallel Algorithm for the Maximal Independent Set Problem
Mark Goldberg, Thomas H. Spencer · SIAM Journal on Computing · 1989
A new parallel algorithm for the maximal independent set problem is constructed. It runs in $O(\log ^4 n)$ time when implemented on a linear number of EREW-processors. This is the first deterministic algorithm for the maximal independent set problem (MIS) whose running time is polylogarithmic and whose processor-time product is optimal up to a polylogarithmic factor.