Enumerating minimal transversals of geometric hypergraphs

Khaled Elbassioni, Imran Rauf, Saurabh Ray

Research output: Contribution to conferencePaper

Abstract

We consider the problem of enumerating all minimal hitting sets of a given hypergraph (V,R), where V is a finite set, called the vertex set and R is a set of subsets of V called the hyperedges. We show that, when the hypergraph admits a balanced subdivision, then a recursive decomposition can be used to obtain efficiently all minimal hitting sets of the hypergraph. We apply this decomposition framework to get incremental polynomial-time algorithms for finding minimal hitting sets and minimal set covers for a number of hypergraphs induced by a set of points and a set of geometric objects. The set of geometric objects includes half-spaces, hyper-rectangles and balls, in fixed dimension. A distinguishing feature of the algorithms we obtain is that they admit an effi- cient global parallel implementation, in the sense that all minimal hitting sets can be generated in polylogarith- mic time in V , R and the total number of minimal transversals T, using a polynomial number of processors.

Original languageEnglish (US)
StatePublished - 2011
Event23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada
Duration: Aug 10 2011Aug 12 2011

Other

Other23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
CountryCanada
CityToronto, ON
Period8/10/118/12/11

ASJC Scopus subject areas

  • Computational Mathematics
  • Geometry and Topology

Fingerprint Dive into the research topics of 'Enumerating minimal transversals of geometric hypergraphs'. Together they form a unique fingerprint.

  • Cite this

    Elbassioni, K., Rauf, I., & Ray, S. (2011). Enumerating minimal transversals of geometric hypergraphs. Paper presented at 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011, Toronto, ON, Canada.