Efficient parallel algorithms on distance hereditary graphs

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)

Abstract

Distance hereditary graphs are graphs in which every two vertices have the same distance in every connected induced subgraph containing them. In this paper, we study properties of distance hereditary graphs from the view point of parallel computations. We present efficient parallel algorithms for finding a minimum weighted connected dominating set, a minimum weighted Steiner tree, 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)43-52
Number of pages10
JournalParallel Processing Letters
Volume9
Issue number1
Publication statusPublished - 1999 Jan 1

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

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

Cite this