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

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Conference article › peer-review

3 Scopus citations

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

Original language	English
Pages (from-to)	20-23
Number of pages	4
Journal	Proceedings of the International Conference on Parallel Processing
State	Published - 1997
Event	Proceedings of the 1997 International Conference on Parallel Processing - Bloomington, IL, USA Duration: 11 Sep 1997 → 15 Sep 1997

Cite this

@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 = "null ; 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

SP - 20

EP - 23

JO - Proceedings of the International Conference on Parallel Processing

JF - Proceedings of the International Conference on Parallel Processing

SN - 0190-3918

Y2 - 11 September 1997 through 15 September 1997

ER -

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

Abstract

Fingerprint

Cite this