Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1985-1989 Copyright 1985-1989 University of Bonn, Department of Computer Science, 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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V