## ＜テクニカルレポート＞Using Maximal Independent Sets to Solve Problems in Parallel

作成者 著者識別子 作成者名 所属機関 所属機関名 Department of Control Engineering and Science Kyushu Institute of Technology 九州工業大学情報工学部制御システム工学科 著者識別子 作成者名 所属機関 所属機関名 Research Institute of Fundamental Information Science Kyushu University 九州大学理学部附属基礎情報学研究施設 英語 Research Institute of Fundamental Information Science, Kyushu University 九州大学理学部附属基礎情報学研究施設 1991-02-18 36 Accepted Manuscript open access 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 144

### 詳細

レコードID 3143 査読無 RIFIS Technical Report || 36 || p1-9 http://www.i.kyushu-u.ac.jp/research/report.html Proc. 17th Intern. Workshop on Graph-Theoretic Concepts in Computer Science WG91, Lecture Notes in Computer Science 570, 126-134, 1991 テクニカルレポート 2009.04.22 2017.01.20