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.
|頁（從 - 到）||20-23|
|期刊||Proceedings of the International Conference on Parallel Processing|
|出版狀態||Published - 1997 一月 1|
|事件||Proceedings of the 1997 International Conference on Parallel Processing - Bloomington, IL, USA|
持續時間: 1997 九月 11 → 1997 九月 15
All Science Journal Classification (ASJC) codes