language: en

An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3

Elias Dahlhaus 1 Marek Karpinski 2 Peter Kelsen 3
TR-92-071 October, 1992

Abstract The paper considers the problem of computing a maximal independent set in a hypergraph (see [3] and [7]). 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 ([5]) for finding a maximal independent set in a graph (or hypergraph of dimension 2). It is the first efficient NC algorithm for finding a maximal independent set in a hypergraph of dimension greater than 2.

1 Department of Computer Science, University of Bonn,
5300 Bonn 1.