An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension

E. Boros, V. Gurvich, K. Elbassioni, L. Khachiyan

Research output: Contribution to journalArticlepeer-review

42 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)253-266
Number of pages14
JournalParallel processing letters
Volume10
Issue number4
DOIs
StatePublished - Dec 2000

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension'. Together they form a unique fingerprint.

Cite this