Efficient parallel algorithms on distance-hereditary graphs (Extended abstract)

Sun-Yuan Hsieh, Tsan sheng Hsu, Chin Wen Ho, Ming Tat Ko, Gen Huey Chen

研究成果: Conference article同行評審

3 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)20-23
頁數4
期刊Proceedings of the International Conference on Parallel Processing
出版狀態Published - 1997 一月 1
事件Proceedings of the 1997 International Conference on Parallel Processing - Bloomington, IL, USA
持續時間: 1997 九月 111997 九月 15

All Science Journal Classification (ASJC) codes

  • 硬體和架構

指紋

深入研究「Efficient parallel algorithms on distance-hereditary graphs (Extended abstract)」主題。共同形成了獨特的指紋。

引用此