An Efficient Parallel Algorithm for the 3MIS Problem
Title | An Efficient Parallel Algorithm for the 3MIS Problem |
Publication Type | Technical Report |
Year of Publication | 1989 |
Authors | Dahlhaus, E., & Karpinski M. |
Other Numbers | 551 |
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. |
URL | http://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 |