In:
Parallel Processing Letters, World Scientific Pub Co Pte Ltd, Vol. 09, No. 01 ( 1999-03), p. 43-52
Abstract:
Distance hereditary graphs are graphs in which every two vertices have the same distance in every connected induced subgraph containing them. In this paper, we study properties of distance hereditary graphs from the view point of parallel computations. We present efficient parallel algorithms for finding a minimum weighted connected dominating set, a minimum weighted Steiner tree, which take O( log n) time using O(n + m) processors on CRCW PRAM, where n and m are the number of vertices and edges of a given graph, respectively. We also find a maximum weighted clique of a distance hereditary graph in O( log 2 n) time using O(n + m) processors on a CREW PRAM.
Type of Medium:
Online Resource
ISSN:
0129-6264
,
1793-642X
DOI:
10.1142/S0129626499000074
Language:
English
Publisher:
World Scientific Pub Co Pte Ltd
Publication Date:
1999