Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, Abt. V
8536

An Efficient Parallel Algorithm for the 3MIS Problem
Elias Dahlhaus, Marek Karpinski
[Download PostScript] [Download PDF]

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^4 n)$ parallel time with $O(n+m)$ processors on a CREW PRAM and is optimal up to a polylogarithmic factor.

Last Change: 11/05/14 at 09:11:05
 English
Universität Bonn -> Institut für Informatik -> Abteilung V