https://scholars.lib.ntu.edu.tw/handle/123456789/118054
標題: | A Faster Implementation of a Parallel Tree Contraction Scheme and Its Application on Distance-Hereditary Graphs | 作者: | Hsieh, Sun-yuan Ho, Chin-Wen Hsu, Tsan-sheng Ko, Ming-Tat Chen, Gen-Huey |
公開日期: | 2000 | 起(迄)頁: | 50-81 | 來源出版物: | Journal of Algorithms | 摘要: | 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. © 2000 Academic Press. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-0002203068&doi=10.1006%2fjagm.1999.1064&partnerID=40&md5=a7c2ee98ccdfb6838d9a09023b685acf | DOI: | 10.1006/jagm.1999.1064 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。