Computing many maximal independent sets for hypergraphs in parallel

Leonid Khachiyan, Endre Boros, Vladimir Gurvich, Khaled Elbassioni

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

A hypergraph ℋ ⊆ 2 V is called uniformly δ-sparse if for every nonempty subset X ⊆ V of vertices, the average degree of the sub-hypergraph of ℋ induced by X is at most δ. We show that there is a deterministic algorithm that, given a uniformly δ-sparse hypergraph ℋ, and a positive integer k, outputs k or all minimal transversals for ℋ in O(δ 1og(1 + k)polylog(δ|V|))-time using |V| O(log δ)k O(δ) processors. Equivalently, the algorithm can be used to compute in parallel k or all maximal independent sets for ℋ.

Original languageBritish English
Pages (from-to)141-152
Number of pages12
JournalParallel Processing Letters
Volume17
Issue number2
DOIs
StatePublished - Jun 2007

Keywords

  • Generation algorithms
  • Global parallel algorithms
  • Hypergraphs
  • Maximal independent sets
  • Minimal transversals

Fingerprint

Dive into the research topics of 'Computing many maximal independent sets for hypergraphs in parallel'. Together they form a unique fingerprint.

Cite this