### A fast parallel algorithm for the maximal independent set problemA fast parallel algorithm for the maximal independent set problem

Access Restriction
Subscribed

 Author Karp, Richard M. ♦ Wigderson, Avi Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1985 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract A parallel algorithm is presented that accepts as input a graph $\textit{G}$ and produces a maximal independent set of vertices in $\textit{G}.$ On a P-RAM without the concurrent write or concurrent read features, the algorithm executes in $\textit{O}((log$ $\textit{n})4)$ time and uses $\textit{O}((\textit{n}/(log$ $\textit{n}))3)$ processors, where $\textit{n}$ is the number of vertices in $\textit{G}.$ The algorithm has several novel features that may find other applications. These include the use of balanced incomplete block designs to replace random sampling by deterministic sampling, and the use of a “dynamic pigeonhole principle” that generalizes the conventional pigeonhole principle. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1985-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 32 Issue Number 4 Page Count 12 Starting Page 762 Ending Page 773

#### Open content in new tab

Source: ACM Digital Library