Title :
Efficient parallel algorithms on distance-hereditary graphs
Author :
Hsieh, Sun-Yuan ; Ho, Chin-Wen ; Hsu, Tsan-Sheng ; Ko, Ming-Tat ; Chen, Gen-Huey
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan
Abstract :
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
Keywords :
computational complexity; computational geometry; parallel algorithms; trees (mathematics); CRCW PRAM; distance-hereditary graph; distance-hereditary graphs; maximum weighted clique; minimum weighted Steiner tree; minimum weighted connected dominating set; parallel algorithms; vertices; Computer science; Information science; Joining processes; Parallel algorithms; Phase change random access memory; Tree graphs;
Conference_Titel :
Parallel Processing, 1997., Proceedings of the 1997 International Conference on
Conference_Location :
Bloomington, IL
Print_ISBN :
0-8186-8108-X
DOI :
10.1109/ICPP.1997.622541
