Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 20-23 |
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 |