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|
|Publication status||Published - 1997 Jan 1|
|Event||Proceedings of the 1997 International Conference on Parallel Processing - Bloomington, IL, USA|
Duration: 1997 Sep 11 → 1997 Sep 15
All Science Journal Classification (ASJC) codes
- Hardware and Architecture