非表示:
キーワード:
-
要旨:
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.
