An efficient parallel algorithm for the efficient domination problem on distance-hereditary graphs

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

In the literature, there are quite a few sequential and parallel algorithms for solving problems on distance-hereditary graphs. With an n-vertex and m-edge distance-hereditary graph G, we show that the efficient domination problem on G can be solved in O(log2n) time using O(n + m) processors on a CREW PRAM. Moreover, if a binary tree representation of G is given, the problem can be optimally solved in O(log n) time using O(n/log n) processors on an EREW PRAM.

Original languageEnglish
Pages (from-to)985-993
Number of pages9
JournalIEEE Transactions on Parallel and Distributed Systems
Volume13
Issue number9
DOIs
Publication statusPublished - 2002 Sep 1

Fingerprint

Binary trees
Parallel algorithms

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this

@article{df55bcb93a0f42daaed943ce027103e5,
title = "An efficient parallel algorithm for the efficient domination 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 and m-edge distance-hereditary graph G, we show that the efficient domination problem on G can be solved in O(log2n) time using O(n + m) processors on a CREW PRAM. Moreover, if a binary tree representation of G is given, the problem can be optimally solved in O(log n) time using O(n/log n) processors on an EREW PRAM.",
author = "Sun-Yuan Hsieh",
year = "2002",
month = "9",
day = "1",
doi = "10.1109/TPDS.2002.1036071",
language = "English",
volume = "13",
pages = "985--993",
journal = "IEEE Transactions on Parallel and Distributed Systems",
issn = "1045-9219",
publisher = "IEEE Computer Society",
number = "9",

}

TY - JOUR

T1 - An efficient parallel algorithm for the efficient domination problem on distance-hereditary graphs

AU - Hsieh, Sun-Yuan

PY - 2002/9/1

Y1 - 2002/9/1

N2 - In the literature, there are quite a few sequential and parallel algorithms for solving problems on distance-hereditary graphs. With an n-vertex and m-edge distance-hereditary graph G, we show that the efficient domination problem on G can be solved in O(log2n) time using O(n + m) processors on a CREW PRAM. Moreover, if a binary tree representation of G is given, the problem can be optimally solved in O(log n) time using O(n/log n) processors on an EREW 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 and m-edge distance-hereditary graph G, we show that the efficient domination problem on G can be solved in O(log2n) time using O(n + m) processors on a CREW PRAM. Moreover, if a binary tree representation of G is given, the problem can be optimally solved in O(log n) time using O(n/log n) processors on an EREW PRAM.

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

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

U2 - 10.1109/TPDS.2002.1036071

DO - 10.1109/TPDS.2002.1036071

M3 - Article

AN - SCOPUS:0036766325

VL - 13

SP - 985

EP - 993

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 9

ER -