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

Research output: Contribution to journalArticlepeer-review

5 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

All Science Journal Classification (ASJC) codes

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

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

Cite this