|
University of Bonn -> Department of Computer Science -> Chair V | ||
CS-Reports 1991 | Copyright 1991 University of Bonn, Department of Computer Science, Abt. V | |
8570
|
An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3
Elias Dahlhaus, Marek Karpinski, Pierre Kelsen [Download PostScript] [Download PDF] The paper considers the problem of computing a maximal independent set in a hypergraph (see \cite{BL} and \cite{KR}). We present an efficient deterministic NC algorithm for finding a maximal independent set in a hypergraph of dimension $3$: the algorithm runs in time $O(\log^4 n)$ time on $n+m$ processors of an EREW PRAM and is optimal up to a polylogarithmic factor. Our algorithm adapts the technique of Goldberg and Spencer (\cite{GS}) for finding a maximal independent set in a graph (or hypergraph of dimension $2$). It is the first NC algorithm for finding a maximal independent set in a hypergraph of dimension greater than 2. |
|
Last Change:
08/18/99 at 13:00:38
Deutsch |
University of Bonn -> Department of Computer Science -> Chair V |