| 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
|
Export Mendeley
rifis-tr-34