Publication Details
Title: An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3
Author: E. Dahlhaus, M. Karpinski, and P. Kelsen
Group: ICSI Technical Reports
Date: October 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-071.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report tr-92-071
Bibliographic Reference:
E. Dahlhaus, M. Karpinski, and P. Kelsen. An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3. ICSI Technical Report tr-92-071, October 1992
Author: E. Dahlhaus, M. Karpinski, and P. Kelsen
Group: ICSI Technical Reports
Date: October 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-071.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report tr-92-071
Bibliographic Reference:
E. Dahlhaus, M. Karpinski, and P. Kelsen. An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3. ICSI Technical Report tr-92-071, October 1992