A Faster Implementation of a Parallel Tree Contraction Scheme and Its Application on Distance-Hereditary Graphs

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

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

We consider a parallel tree contraction scheme which in each contraction phase removes leaves and nodes in the maximal chains. Let T(n) and P(n) denote the time and processor complexity required to compute the all nearest smaller values (ANSV) and the minimum of n values for input elements drawn from the integer domain [1 . . . n]. In this paper, we give a faster implementation of the tree contraction scheme which takes O(log n · T(n)) time using P(n) processors on an arbitrary CRCW PRAM. The current best results of T(n) and P(n) are O(log log log n) and O(n/log log log n), respectively. To our knowledge, the previously best known implementation needs O(log2 n) time using O(n/log n) processors on an EREW PRAM. The faster parallel implementation of the tree contraction scheme may be of interests by itself. We then show the above scheme can be utilized to solve problems on distance-hereditary graphs. We provide a data structure to represent a connected distance-hereditary graph in the form of a rooted tree. By applying the above tree contraction scheme on our data structure together with graph theoretical properties, we solve the problems of finding a minimum connected γ-dominating set and finding a minimum γ-dominating clique on a distance-hereditary graph in O(log n · T(n)) time using O(P(n) + (n + m)/T(n)) processors on an arbitrary CRCW PRAM, where n and m are the number of vertices and edges of the given graph, respectively. The above result implies several other problems related to the minimum γ-dominating clique problem can be solved with the same parallel complexities.

Original languageEnglish
Pages (from-to)50-81
Number of pages32
JournalJournal of Algorithms
Volume35
Issue number1
DOIs
StatePublished - Apr 2000

Fingerprint

Dive into the research topics of 'A Faster Implementation of a Parallel Tree Contraction Scheme and Its Application on Distance-Hereditary Graphs'. Together they form a unique fingerprint.

Cite this