| 作成者 |
|
|
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
By using the vertex coloring technique, we give a fast parallel algorithm that finds a maximal vertex-induced subgraph of degree at most $ kappa $ , where $ kappa $ is a given constant. This algorithm... runs in O (log* n) time using O(n) processors on an EREW PRAM for a constant degree graph G = (V, E) with mid V mid = n. We also describe an O(log* m) time O(m) processor EREW PRAM algorithm for finding a maximal edge-induced subgraph of degree at most k, where m = mid Emid. For constant degree graphs, we show that the coloring technique works very successfully to devise faster parallel algorithms with less number of processors.続きを見る
|
Mendeley出力
rifis-tr-34