A global parallel algorithm for the hypergraph transversal problem
We consider the problem of finding all minimal transversals of a hypergraph H subset of 2(V), 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(vertical bar V vertical bar, vertical bar H vertical bar, k) assuming poly(vertical bar V vertical bar, vertical bar H vertical bar, 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. (c) 2006 Elsevier B.V. All rights reserved.
global parallel algorithm hypergraph minimal transversal bounded dimension conformal hypergraph dualization incremental generating maximal independent set parallel processing