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