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

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

Research output: Contribution to journalConference articlepeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)20-23
Number of pages4
JournalProceedings of the International Conference on Parallel Processing
Publication statusPublished - 1997 Jan 1
EventProceedings of the 1997 International Conference on Parallel Processing - Bloomington, IL, USA
Duration: 1997 Sep 111997 Sep 15

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Efficient parallel algorithms on distance-hereditary graphs (Extended abstract)'. Together they form a unique fingerprint.

Cite this