A Parallel Algorithm for the Maximal Co-Hitting Set Problem

Takayoshi SHOUDAI  Satoru MIYANO  

IEICE TRANSACTIONS on Information and Systems   Vol.E76-D   No.2   pp.296-298
Publication Date: 1993/02/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithm and Computational Complexity
algorithm and computational complexity,  parallel algorithm,  maximal co-hitting set problem,  minimal set cover problem,  maximal independent set problem,  

Full Text: PDF>>
Buy this Article

Let C{c1, , cm} be a family of subsets of a finite set S{1, , n}, a subset S of S is a co-hitting set if S contains no element of C as a subset. By using an O((log n)2) time EREW PRAM algorithm for a maximal independent set problem (MIS), we show that a maximal co-hitting set for S can be computed on an EREW PRAN in time O(αβ(log(nm))2) using O(n2 m) processors, where αmax{|cii1, , n} and βmax{|djj1, , n} with dj{ci|jci}. This implies that if αβO((log(nm))k) then the problem is solvable in NC.