Creator |
|
|
Language |
|
Publisher |
|
|
Date |
|
Source Title |
|
Vol |
|
Publication Type |
|
Access Rights |
|
Related DOI |
|
|
Related URI |
|
|
Relation |
|
|
Abstract |
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.show more
|