COMPUTING MANY MAXIMAL INDEPENDENT SETS FOR HYPERGRAPHS IN PARALLEL
Leonid Khachiyan, Endre Boros, Vladimir A. Gurvich, Khaled Elbassioni · Parallel Processing Letters · 2007
A hypergraph [Formula: see text] is called uniformly δ-sparse if for every nonempty subset X ⊆ V of vertices, the average degree of the sub-hypergraph of [Formula: see text] induced by X is at most δ. We show that there is a deterministic algorithm that, given a uniformly δ-sparse hypergraph [Formula: see text], and a positive integer k, outputs k or all minimal transversals for [Formula: see text] in O(δ log (1 + k) polylog (δ|V|))-time using |V| O( log δ) k O(δ) processors. Equivalently, the algorithm can be used to compute in parallel k or all maximal independent sets for [Formula: see text].