
University of Bonn > Department of Computer Science > Chair V  
CSReports 19851989  Copyright 19851989 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 