<テクニカルレポート>
Using Maximal Independent Sets to Solve Problems in Parallel

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 By using an $ 0 ((log n)^2) $ time EREW PRAM algorithm for a maximal independent set problem (MIS), we show the following two results: (1) Given a graph, the maximal vertex-induced subgraph satisfying... a hereditary graph property $ pi $ can be found in time $ 0 ( Delta ^lambda ^(pi)T_pi(n)(log n)^2) $ using a polynomial number of processors, where $ lamda(pi) $ is the maximum of diameters of minimal graphs violating $ pi $ and $ T_pi(n) $ is the time needed to decide whether a graph with n vertices satisfies $ pi $. (2) Given a family $ C = {c_1. . . ,c_m} $ of subsets of a finite set S = {I,. . . , n} with $ S = U^m_i=_1 ci $, a minimal set cover for S can be computed on an EREW PRAM in time $ O(alpha\beta(log(n+m))^2) $ using a polynomial number of processors, where $ alpha = max{mid ci midmid i=1,...,m} $ and $ \beta = max{mid d_j /mid mid j=1,...n} $.続きを見る

本文情報を非表示

rifis-tr-36 pdf 630 KB 86  

詳細

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