|
Universität Bonn -> Institut für Informatik -> Abteilung V | ||
CS-APX-Reports 1985-1989 | Copyright 1985-1989 Universität Bonn, Institut für Informatik, 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
English |
Universität Bonn -> Institut für Informatik -> Abteilung V |