A global parallel algorithm for the hypergraph transversal problem

Leonid Khachiyan, Endre Boros, Khaled Elbassioni, Vladimir Gurvich

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

We consider the problem of finding all minimal transversals of a hypergraph H ⊆ 2V, given by an explicit list of its hyperedges. We give a new decomposition technique for solving the problem with the following advantages: (i) Global parallelism: for certain classes of hypergraphs, e.g., hypergraphs of bounded edge size, and any given integer k, the algorithm outputs k minimal transversals of H in time bounded by polylog (| V |, | H |, k) assuming poly (| V |, | H |, k) number of processors. Except for the case of graphs, none of the previously known algorithms for solving the same problem exhibit this feature. (ii) Using this technique, we also obtain new results on the complexity of generating minimal transversals for new classes of hypergraphs, namely hypergraphs of bounded dual-conformality, and hypergraphs in which every edge intersects every minimal transversal in a bounded number of vertices.

Original languageEnglish (US)
Pages (from-to)148-155
Number of pages8
JournalInformation Processing Letters
Volume101
Issue number4
DOIs
StatePublished - Feb 28 2007

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Bounded dimension
  • Conformal hypergraph
  • Dualization
  • Global parallel algorithm
  • Hypergraph
  • Incremental generating
  • Maximal independent set
  • Minimal transversal
  • Parallel processing

Fingerprint

Dive into the research topics of 'A global parallel algorithm for the hypergraph transversal problem'. Together they form a unique fingerprint.

Cite this