AN EFFICIENT INCREMENTAL ALGORITHM FOR GENERATING ALL MAXIMAL INDEPENDENT SETS IN HYPERGRAPHS OF BOUNDED DIMENSION
Endre Boros, Vladimir Gurvich, Khaled Elbassioni, Leonid Khachiyan · Parallel Processing Letters · 2000
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.