DIMACS TR: 2004-31
A Global Parallel Algorithm for Finding All Minimal Transversals of Hypergraphs of Bounded Edge-size
Authors: E. Boros, K. Elbassioni, V. Gurvich and L. Khachiyan
ABSTRACT
We give a deterministic parallel algorithm that, for any given hypergraph
$\cH\subseteq 2^V$ with maximum edge-size less than $\delta$,
outputs all minimal transversals (or equivalently all maximal
independent sets) of $\cH$ in time
$O(\delta^2\log^2 n\log m)$ using $O(n^{\delta\log\delta+2}
m^{\delta})$ processors on a CREW-PRAM,
where $m$ is the total number of minimal transversals and $n=|V|$. This
algorithm can be modified so that, for any integer
$k$, it outputs $k$ minimal transversals of $\cH$ in time $O(\delta^2\log^2
n \log k+T)$ using $O(n^{\delta\log\delta+1} k^{\delta}+k\Pi)$
processors, where $T$ and $\Pi$ are respectively the parallel time and
the number of processors required to generate a
single minimal transversal of $\cH$. The latter problem is known to be
in RNC for hypergraphs of bounded edge-size.
This strengthens and generalizes a previously known result for
graphs. We also obtain a similar result for hypergraphs whose
transversal hypergraphs are $\delta$-conformal for some constant
$\delta$.
Key Words:
Bounded dimension, conformal hypergraph, dualization, global
parallel algorithm, hypergraph, incremental generating,
maximal independent set, minimal transversal.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-31.ps.gz
DIMACS Home Page