An Efficient Parallel Algorithm for the 3MIS Problem

TitleAn Efficient Parallel Algorithm for the 3MIS Problem
Publication TypeTechnical Report
Year of Publication1989
AuthorsDahlhaus, E., & Karpinski M.
Other Numbers551
Abstract

The paper considers the problem of computing a maximal independent set in hypergraphs (see [Karp, Ramachandran 88] and [Beame, Luby 89]). We present an efficient deterministic parallel algorithm for the case when the maximal cardinality of any hyperedge is 3. The algorithm works in O((log superscript 4) n) parallel time with O(n + m) processors on a CREW PRAM and is optimal up to a polylogarithmic factor.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-89-52.pdf
Bibliographic Notes

ICSI Technical Report TR-89-052

Abbreviated Authors

E. Dahlhaus and M. Karpinski

ICSI Publication Type

Technical Report