Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/14606
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Stojmenović, Ivan | en_US |
dc.contributor.author | Langston M. | en_US |
dc.date.accessioned | 2020-03-03T14:56:42Z | - |
dc.date.available | 2020-03-03T14:56:42Z | - |
dc.date.issued | 1988-01-01 | - |
dc.identifier.issn | 00063835 | en_US |
dc.identifier.uri | https://open.uns.ac.rs/handle/123456789/14606 | - |
dc.description.abstract | In a recent paper published in this journal, R. Chang and R. Lee purport to devise an O(N log N) time minimal spanning tree algorithm for N points in the plane that is based on a divide-and-conquer strategy using Voronoi diagrams. In this brief note, we present families of problem instances to show that the Chang-Lee worst-case timing analysis is incorrect, resulting in a time bound of O(N2 log N). Since it is known that alternate, truly O(N log N) time algorithms are available anyway, the general utility of the Chang-Lee algorithm is questionable. © 1988 BIT Foundations. | en |
dc.relation.ispartof | BIT | en |
dc.title | On a proposed divide-and-conquer minimal spanning tree algorithm | en_US |
dc.type | Journal/Magazine Article | en_US |
dc.identifier.doi | 10.1007/BF01954898 | - |
dc.identifier.scopus | 2-s2.0-34250094911 | - |
dc.identifier.url | https://api.elsevier.com/content/abstract/scopus_id/34250094911 | - |
dc.description.version | Unknown | en_US |
dc.relation.lastpage | 789 | en |
dc.relation.firstpage | 785 | en |
dc.relation.issue | 4 | en |
dc.relation.volume | 28 | en |
item.grantfulltext | none | - |
item.fulltext | No Fulltext | - |
Appears in Collections: | Naučne i umetničke publikacije |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.