## ＜テクニカルレポート＞A Parallel Algorithm for the Maximal Co-Hitting Set Problem

作成者 著者識別子 作成者名 所属機関 所属機関名 Faculty of Engineering, Yamaguchi University 山口大学工学部 著者識別子 作成者名 所属機関 所属機関名 Research Institute of Fundamental Information Science Kyushu University 九州大学理学部附属基礎情報学研究施設 英語 Research Institute of Fundamental Information Science, Kyushu University 九州大学理学部附属基礎情報学研究施設 1992-10-30 65 Accepted Manuscript open access RIFIS Technical Report || 65 || p1-7 http://www.i.kyushu-u.ac.jp/research/report.html Let $C = left{c_1,...,c_m \right}$ be a family of subsets of a finite set $S = left{1,...,n \right}$, a subset S' of S is a co-hitting set if S' contains no element of C as a subset. By using an $... O left((log n)^2\right)$ 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 PRAM in time $Oleft(alpha \beta(log(n+m))^2\right)$ using $Oleft(n^2m\right)$ processors, where $alpha = maxleft{mid ci midmid i = 1,...,m \right}$ and $/beta = max left{mid d_j mid mid j = 1,...,n\right}$ with $d_j = left{ci mid j \varepsilon ci\right}$. This implies that if $alpha \beta = O left((log(n+ m))^k\right)$ then the problem is solvable in NC.続きを見る

### 本文ファイル

rifis-tr-65 pdf 403 KB 176

### 詳細

レコードID 3167 査読無 algorithm and computational complexity parallel algorithm maximal co-hitting set problem minimal set cover problem maximal independent set problem IEICE Transactions on Information and Systems E76-D, No. 2, 296-298,1993 テクニカルレポート 2009.04.22 2017.01.20