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

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 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 52  

詳細

レコードID
査読有無
関連情報
主題
注記
タイプ
登録日 2009.04.22
更新日 2017.01.20