Title: Constructing a Maximal Independent Set in Parallel
Abstract: 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)/\log n)$ processors and runs in $O(\log^3 n)$ time. This reduces by a factor of $\log n$ both the running time and the processor count of the previously fastest deterministic algorithm that solves the problem using a linear number of processors.
Publication Year: 1989
Publication Date: 1989-08-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 82
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot