In this paper, we present efficient parallel algorithms for finding a minimum weighted connected dominating set, a minimum weighted Steiner tree for a distance-hereditary graph which take O(log n) time using O(n+m) processors on a 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(log2 n) time using O(n+m) processors on a CREW PRAM.
|Number of pages||4|
|Journal||Proceedings of the International Conference on Parallel Processing|
|State||Published - 1997|
|Event||Proceedings of the 1997 International Conference on Parallel Processing - Bloomington, IL, USA|
Duration: 11 Sep 1997 → 15 Sep 1997