| Creator |
|
|
|
| Language |
|
| Publisher |
|
|
|
| Date |
|
| Source Title |
|
| Vol |
|
| Publication Type |
|
| Access Rights |
|
| Related DOI |
|
|
|
| Related URI |
|
|
|
| Relation |
|
|
|
| Abstract |
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.show more
|
Export Mendeley
rifis-tr-65