TY - JOUR
T1 - A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
AU - Elbassioni, Khaled
AU - Rauf, Imran
AU - Ray, Saurabh
N1 - Publisher Copyright:
© 2018 Elsevier B.V.
PY - 2019/5/3
Y1 - 2019/5/3
N2 - 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.
AB - 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.
KW - Enumeration algorithms
KW - Geometric hypergraphs
KW - Minimal set covers
KW - Minimal transversals
UR - http://www.scopus.com/inward/record.url?scp=85054021976&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85054021976&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2018.09.027
DO - 10.1016/j.tcs.2018.09.027
M3 - Article
AN - SCOPUS:85054021976
SN - 0304-3975
VL - 767
SP - 26
EP - 33
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -