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

Sun Yuan Hsieh, Gen Huey Chen, Chin Wen Ho

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish
Title of host publicationAdvances in Computing Science ASIAN 1998 - 4th Asian Computing Science Conference, Proceedings
EditorsJieh Hsiang, Atsushi Ohori
PublisherSpringer Verlag
Pages113-124
Number of pages12
ISBN (Print)3540653880, 9783540653882
DOIs
Publication statusPublished - 1998 Jan 1
Event4th Asian Computing Science Conference, ASIAN 1998 - Manila, Philippines
Duration: 1998 Dec 81998 Dec 10

Publication series

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

Other

Other4th Asian Computing Science Conference, ASIAN 1998
CountryPhilippines
CityManila
Period98-12-0898-12-10

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs'. Together they form a unique fingerprint.

  • 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