Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

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

Powered by Zope