## DIMACS TR: 2000-21

## An Incremental RNC Algorithm for Generating All Maximal Independent Sets in Hypergraphs of Bounded Dimension

### Authors: E. Boros, K. Elbassioni, V. Gurvich and L. Khachiyan

**
ABSTRACT
**

We show that for hypergraphs of bounded edge size, the problem of
extending a given list of maximal independent sets is NC-reducible to the
computation of an arbitrary maximal independent set for an induced sub-
hypergraph. The latter problem is known to be in RNC. In particular, our
reduction yields an incremental RNC dualization algorithm for hypergraphs of
bounded edge size, a problem previously known to be solvable in polynomial
incremental time. We also give a similar parallel algorithm for the
dualization problem on the product of arbitrary lattices which have
a bounded number of immediate predecessors for each element.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-21.ps.gz

DIMACS Home Page