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