https://scholars.lib.ntu.edu.tw/handle/123456789/624641
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | Liu C.-H | en_US |
dc.contributor.author | Montanari S. | en_US |
dc.contributor.author | CHIH-HUNG LIU | en_US |
dc.date.accessioned | 2022-11-11T02:58:57Z | - |
dc.date.available | 2022-11-11T02:58:57Z | - |
dc.date.issued | 2018 | - |
dc.identifier.issn | 01784617 | - |
dc.identifier.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85013648316&doi=10.1007%2fs00453-017-0292-6&partnerID=40&md5=595cbf5f2641714747badc30da71df48 | - |
dc.identifier.uri | https://scholars.lib.ntu.edu.tw/handle/123456789/624641 | - |
dc.description.abstract | We study the diameter of a spanning tree, i.e., the length of its longest simple path, under the imprecise points model, in which each point is assigned its own occurrence region instead of an exact location. We prove that the minimum diameter of a spanning tree of n points each of which is selected from its respective disk (or axis-parallel square) is polynomial-time computable, contrasting with the fact that minimizing the cost of a spanning tree, i.e. the sum of its edge lengths, for imprecise points is known to be NP-hard. This difference is very interesting since for exact points minimizing the cost seems faster than minimizing the diameter [O(nlog n) versus almost cubic running time]. As the first work regarding the minimum diameter of a spanning tree for imprecise points, our main objective is to investigate essential properties that distinguish the problem from NP-hard instead of minimizing the running time [O(n9) for general disks or O(n6) for unit ones]. Our algorithm mainly utilizes farthest-site Voronoi diagrams for disks and axis-parallel squares, and these diagrams would have their own merits. © 2017, Springer Science+Business Media New York. | - |
dc.relation.ispartof | Algorithmica | - |
dc.subject | Computational geometry; Imprecise data; Minimum diameter spanning trees; Voronoi diagrams | - |
dc.subject.other | Graphic methods; Polynomial approximation; Edge length; Imprecise data; Minimum diameter spanning tree; Minimum diameters; Polynomial-time; Running time; Spanning tree; Voronoi diagrams; Computational geometry | - |
dc.title | Minimizing the Diameter of a Spanning Tree for Imprecise Points | en_US |
dc.type | journal article | en |
dc.identifier.doi | 10.1007/s00453-017-0292-6 | - |
dc.identifier.scopus | 2-s2.0-85013648316 | - |
dc.relation.pages | 801-826 | - |
dc.relation.journalvolume | 80 | - |
dc.relation.journalissue | 2 | - |
item.openairetype | journal article | - |
item.openairecristype | http://purl.org/coar/resource_type/c_6501 | - |
item.cerifentitytype | Publications | - |
item.fulltext | no fulltext | - |
item.grantfulltext | none | - |
crisitem.author.dept | Electrical Engineering | - |
crisitem.author.orcid | 0000-0001-9683-5982 | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。