Efficient parallel algorithms on distance hereditary graphs

研究成果: Article同行評審

11 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)43-52
頁數10
期刊Parallel Processing Letters
9
發行號1
出版狀態Published - 1999 一月 1

All Science Journal Classification (ASJC) codes

  • 軟體
  • 理論電腦科學
  • 硬體和架構

指紋

深入研究「Efficient parallel algorithms on distance hereditary graphs」主題。共同形成了獨特的指紋。

引用此