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