TY - JOUR

T1 - A global parallel algorithm for the hypergraph transversal problem

AU - Khachiyan, Leonid

AU - Boros, Endre

AU - Elbassioni, Khaled

AU - Gurvich, Vladimir

N1 - Funding Information:
✩ This research was supported in part by the National Science Foundation (Grant IIS-0118635) and by DIMACS, the National Science Foundation’s Center for Discrete Mathematics and Theoretical Computer Science. * Corresponding author. E-mail addresses: boros@rutcor.rutgers.edu (E. Boros), elbassio@mpi-sb.mpg.de (K. Elbassioni), gurvich@rutcor.rutgers.edu (V. Gurvich).

PY - 2007/2/28

Y1 - 2007/2/28

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

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

KW - Bounded dimension

KW - Conformal hypergraph

KW - Dualization

KW - Global parallel algorithm

KW - Hypergraph

KW - Incremental generating

KW - Maximal independent set

KW - Minimal transversal

KW - Parallel processing

UR - http://www.scopus.com/inward/record.url?scp=33845429198&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2006.09.006

DO - 10.1016/j.ipl.2006.09.006

M3 - Article

AN - SCOPUS:33845429198

SN - 0020-0190

VL - 101

SP - 148

EP - 155

JO - Information Processing Letters

JF - Information Processing Letters

IS - 4

ER -