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(log/sup 2/ n) time using O(n+m) processors on a CREW PRAM.
['Sun-Yaan Hsieh', 'Chin-Wen Ho', 'Tsan-sheng Hsu', 'Ming-Tat Ko', 'Gen-Huey Chen']
Efficient parallel algorithms on distance-hereditary graphs