A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs

Author Affiliation

Imran Rauf is Assistant Professor at Institute of Business Administration (IBA), Karachi

Faculty / School

Faculty of Computer Sciences (FCS)

Department

Department of Computer Science

Was this content written or created while at IBA?

Yes

Document Type

Article

Source Publication

Theoretical Computer Science

ISSN

0304-3975

Disciplines

Computer Sciences | Mathematics

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 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.

Indexing Information

HJRS - W Category, Scopus, Web of Science - Science Citation Index Expanded (SCI)

Publication Status

Published

Link to Full Text

Share

COinS