Publication Details
Title: An Efficient Parallel Algorithm for the 3MIS Problem
Author: E. Dahlhaus and M. Karpinski
Group: ICSI Technical Reports
Date: September 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-52.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-89-052
Bibliographic Reference:
E. Dahlhaus and M. Karpinski. An Efficient Parallel Algorithm for the 3MIS Problem. ICSI Technical Report TR-89-052, September 1989
Author: E. Dahlhaus and M. Karpinski
Group: ICSI Technical Reports
Date: September 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-52.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-89-052
Bibliographic Reference:
E. Dahlhaus and M. Karpinski. An Efficient Parallel Algorithm for the 3MIS Problem. ICSI Technical Report TR-89-052, September 1989