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

TitleAn Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3
Publication TypeTechnical Report
Year of Publication1992
AuthorsDahlhaus, E., Karpinski M., & Kelsen P.
Other Numbers776
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.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1992/tr-92-071.pdf
Bibliographic Notes

ICSI Technical Report tr-92-071

Abbreviated Authors

E. Dahlhaus, M. Karpinski, and P. Kelsen

ICSI Publication Type

Technical Report