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

Sun yuan Hsieh; Tsan sheng Hsu; Chin Wen Ho; Ming Tat Ko; Gen Huey Chen

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

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

資訊工程學系

研究成果: 雜誌貢獻 › 會議論文 › 同行評審

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(log² n) time using O(n+m) processors on a CREW PRAM.

原文	???core.languages.en_GB???
頁（從 - 到）	20-23
頁數	4
期刊	Proceedings of the International Conference on Parallel Processing
出版狀態	已出版 - 1997
事件	Proceedings of the 1997 International Conference on Parallel Processing - Bloomington, IL, USA 持續時間: 11 9月 1997 → 15 9月 1997

引用此

@article{cb499167b3544a6c83022a4241be1dd9,

title = "Efficient parallel algorithms on distance-hereditary graphs (Extended abstract)",

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.",

author = "Hsieh, {Sun yuan} and Hsu, {Tsan sheng} and Ho, {Chin Wen} and Ko, {Ming Tat} and Chen, {Gen Huey}",

year = "1997",

language = "???core.languages.en_GB???",

pages = "20--23",

journal = "Proceedings of the International Conference on Parallel Processing",

issn = "0190-3918",

note = "Proceedings of the 1997 International Conference on Parallel Processing ; Conference date: 11-09-1997 Through 15-09-1997",

}

TY - JOUR

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

AU - Hsieh, Sun yuan

AU - Hsu, Tsan sheng

AU - Ho, Chin Wen

AU - Ko, Ming Tat

AU - Chen, Gen Huey

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0030714517&partnerID=8YFLogxK

M3 - 會議論文

AN - SCOPUS:0030714517

SN - 0190-3918

SP - 20

EP - 23

JO - Proceedings of the International Conference on Parallel Processing

JF - Proceedings of the International Conference on Parallel Processing

T2 - Proceedings of the 1997 International Conference on Parallel Processing

Y2 - 11 September 1997 through 15 September 1997

ER -

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

摘要

指紋

引用此