Department of Computer Science
 
Chair V

 
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