https://scholars.lib.ntu.edu.tw/handle/123456789/624648
標題: | Minimizing the diameter of a spanning tree for imprecise points | 作者: | Liu C.-H Montanari S. CHIH-HUNG LIU |
公開日期: | 2015 | 卷: | 9472 | 起(迄)頁: | 381-392 | 來源出版物: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | 摘要: | 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 an own occurrence disk instead of an exact location. We prove that the minimum diameter of a spanning tree for n points each of which is selected from its occurrence disk can be computed in O(n9) time for arbitrary disks and in O(n6) time for unit ones. If the disks are disjoint, we improve the run-time respectively to O(n8log2n) and O(n5). These results contrast with the fact that minimizing the sum of the edge lengths of a spanning tree for imprecise points is NP-hard. © Springer-Verlag Berlin Heidelberg 2015. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84952025574&doi=10.1007%2f978-3-662-48971-0_33&partnerID=40&md5=a9dee8d2298496454e6840e117cfd5e1 https://scholars.lib.ntu.edu.tw/handle/123456789/624648 |
ISSN: | 03029743 | DOI: | 10.1007/978-3-662-48971-0_33 | SDG/關鍵字: | Computers; Edge length; Minimum diameters; NP-hard; Runtimes; Spanning tree; Artificial intelligence |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。