A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
Faculty / School
Faculty of Computer Sciences (FCS)
Department of Computer Science
Was this content written or created while at IBA?
Theoretical Computer Science
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 efficient global parallel implementation, in the sense that all minimal hitting sets can be generated in polylogarithmic time in |V|, |R| and the total number of minimal transversals M, using a polynomial number of processors. For half-spaces in R 2 , we show that the above two enumeration problems can be solved, using a different technique, with amortized polynomial delay.
HJRS - W Category, Scopus, Web of Science - Science Citation Index Expanded (SCI)
Elbassioni, K., Rauf, I., & Ray, S. (2019). A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs. Theoretical Computer Science, 767, 26-33. Retrieved from https://ir.iba.edu.pk/faculty-research-articles/98