An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3
Title | An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3 |
Publication Type | Technical Report |
Year of Publication | 1992 |
Authors | Dahlhaus, E., Karpinski M., & Kelsen P. |
Other Numbers | 776 |
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. |
URL | http://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 |