| 作成者 |
|
|
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
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.続きを見る
|
Mendeley出力
rifis-tr-65