An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs

Sun Yuan Hsieh; Gen Huey Chen; Chin Wen Ho

doi:10.1007/3-540-49366-2_10

An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs

Sun Yuan Hsieh, Gen Huey Chen, Chin Wen Ho

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In the literature, there are quite a few sequential and parallel algorithms for solving problems on distance-hereditary graphs. With an n-vertex distance-hereditary graph G, we show that the perfect dominating set problem on G can be solved in O(log² n) time using O(n+m) procesors on a CREW PRAM.

Original language	English
Title of host publication	Advances in Computing Science ASIAN 1998 - 4th Asian Computing Science Conference, Proceedings
Editors	Jieh Hsiang, Atsushi Ohori
Publisher	Springer Verlag
Pages	113-124
Number of pages	12
ISBN (Print)	3540653880, 9783540653882
DOIs	https://doi.org/10.1007/3-540-49366-2_10
State	Published - 1998
Event	4th Asian Computing Science Conference, ASIAN 1998 - Manila, Philippines Duration: 8 Dec 1998 → 10 Dec 1998

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1538
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	4th Asian Computing Science Conference, ASIAN 1998
Country/Territory	Philippines
City	Manila
Period	8/12/98 → 10/12/98

Access to Document

10.1007/3-540-49366-2_10

Cite this

Hsieh, S. Y., Chen, G. H., & Ho, C. W. (1998). An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs. In J. Hsiang, & A. Ohori (Eds.), Advances in Computing Science ASIAN 1998 - 4th Asian Computing Science Conference, Proceedings (pp. 113-124). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1538). Springer Verlag. https://doi.org/10.1007/3-540-49366-2_10

Hsieh, Sun Yuan ; Chen, Gen Huey ; Ho, Chin Wen. / An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs. Advances in Computing Science ASIAN 1998 - 4th Asian Computing Science Conference, Proceedings. editor / Jieh Hsiang ; Atsushi Ohori. Springer Verlag, 1998. pp. 113-124 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a0dac101d5ec49fd99bbe0c8a76d1578,

title = "An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs",

abstract = "In the literature, there are quite a few sequential and parallel algorithms for solving problems on distance-hereditary graphs. With an n-vertex distance-hereditary graph G, we show that the perfect dominating set problem on G can be solved in O(log2 n) time using O(n+m) procesors on a CREW PRAM.",

author = "Hsieh, {Sun Yuan} and Chen, {Gen Huey} and Ho, {Chin Wen}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1998.; 4th Asian Computing Science Conference, ASIAN 1998 ; Conference date: 08-12-1998 Through 10-12-1998",

year = "1998",

doi = "10.1007/3-540-49366-2_10",

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

isbn = "3540653880",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "113--124",

editor = "Jieh Hsiang and Atsushi Ohori",

booktitle = "Advances in Computing Science ASIAN 1998 - 4th Asian Computing Science Conference, Proceedings",

}

Hsieh, SY, Chen, GH & Ho, CW 1998, An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs. in J Hsiang & A Ohori (eds), Advances in Computing Science ASIAN 1998 - 4th Asian Computing Science Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1538, Springer Verlag, pp. 113-124, 4th Asian Computing Science Conference, ASIAN 1998, Manila, Philippines, 8/12/98. https://doi.org/10.1007/3-540-49366-2_10

An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs. / Hsieh, Sun Yuan; Chen, Gen Huey; Ho, Chin Wen.
Advances in Computing Science ASIAN 1998 - 4th Asian Computing Science Conference, Proceedings. ed. / Jieh Hsiang; Atsushi Ohori. Springer Verlag, 1998. p. 113-124 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1538).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs

AU - Hsieh, Sun Yuan

AU - Chen, Gen Huey

AU - Ho, Chin Wen

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1998.

PY - 1998

Y1 - 1998

N2 - In the literature, there are quite a few sequential and parallel algorithms for solving problems on distance-hereditary graphs. With an n-vertex distance-hereditary graph G, we show that the perfect dominating set problem on G can be solved in O(log2 n) time using O(n+m) procesors on a CREW PRAM.

AB - In the literature, there are quite a few sequential and parallel algorithms for solving problems on distance-hereditary graphs. With an n-vertex distance-hereditary graph G, we show that the perfect dominating set problem on G can be solved in O(log2 n) time using O(n+m) procesors on a CREW PRAM.

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

U2 - 10.1007/3-540-49366-2_10

DO - 10.1007/3-540-49366-2_10

M3 - 會議論文篇章

AN - SCOPUS:84947922354

SN - 3540653880

SN - 9783540653882

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 113

EP - 124

BT - Advances in Computing Science ASIAN 1998 - 4th Asian Computing Science Conference, Proceedings

A2 - Hsiang, Jieh

A2 - Ohori, Atsushi

PB - Springer Verlag

T2 - 4th Asian Computing Science Conference, ASIAN 1998

Y2 - 8 December 1998 through 10 December 1998

ER -

Hsieh SY, Chen GH, Ho CW. An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs. In Hsiang J, Ohori A, editors, Advances in Computing Science ASIAN 1998 - 4th Asian Computing Science Conference, Proceedings. Springer Verlag. 1998. p. 113-124. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-49366-2_10

An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this