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 |