https://scholars.lib.ntu.edu.tw/handle/123456789/118054
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | Hsieh, Sun-yuan | en |
dc.contributor.author | Ho, Chin-Wen | en |
dc.contributor.author | Hsu, Tsan-sheng | en |
dc.contributor.author | Ko, Ming-Tat | en |
dc.contributor.author | Chen, Gen-Huey | en |
dc.creator | Hsieh, Sun-Yuan; Ho, Chin-Wen; Hsu, Tsan-Sheng; Ko, Ming-Tat; Chen, Gen-Huey | - |
dc.date | 2000 | en |
dc.date.accessioned | 2009-04-29T04:13:40Z | - |
dc.date.accessioned | 2018-07-05T01:48:54Z | - |
dc.date.available | 2009-04-29T04:13:40Z | - |
dc.date.available | 2018-07-05T01:48:54Z | - |
dc.date.issued | 2000 | - |
dc.identifier.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-0002203068&doi=10.1006%2fjagm.1999.1064&partnerID=40&md5=a7c2ee98ccdfb6838d9a09023b685acf | - |
dc.description.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. © 2000 Academic Press. | - |
dc.format | application/pdf | en |
dc.format.extent | 267698 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language | en | en |
dc.language.iso | en_US | - |
dc.relation | Journal of Algorithms 35 (1): 50-81 | en |
dc.relation.ispartof | Journal of Algorithms | en_US |
dc.title | A Faster Implementation of a Parallel Tree Contraction Scheme and Its Application on Distance-Hereditary Graphs | en |
dc.type | journal article | en |
dc.identifier.doi | 10.1006/jagm.1999.1064 | - |
dc.identifier.scopus | 2-s2.0-0002203068 | - |
dc.relation.pages | 50-81 | - |
dc.identifier.uri.fulltext | http://ntur.lib.ntu.edu.tw/bitstream/246246/154722/1/37.pdf | - |
item.fulltext | with fulltext | - |
item.cerifentitytype | Publications | - |
item.openairecristype | http://purl.org/coar/resource_type/c_6501 | - |
item.grantfulltext | open | - |
item.openairetype | journal article | - |
item.languageiso639-1 | en_US | - |
crisitem.author.dept | Networking and Multimedia | - |
crisitem.author.dept | Computer Science and Information Engineering | - |
crisitem.author.orcid | 0000-0002-6968-6747 | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。