Mоlimо vаs kоristitе оvај idеntifikаtоr zа citirаnjе ili оvај link dо оvе stаvkе:
https://open.uns.ac.rs/handle/123456789/14606
Nаziv: | On a proposed divide-and-conquer minimal spanning tree algorithm | Аutоri: | Stojmenović, Ivan Langston M. |
Dаtum izdаvаnjа: | 1-јан-1988 | Čаsоpis: | BIT | Sažetak: | 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. | URI: | https://open.uns.ac.rs/handle/123456789/14606 | ISSN: | 00063835 | DOI: | 10.1007/BF01954898 |
Nаlаzi sе u kоlеkciјаmа: | Naučne i umetničke publikacije |
Prikаzаti cеlоkupаn zаpis stаvki
Prеglеd/i stаnicа
8
Prоtеklа nеdеljа
8
8
Prоtеkli mеsеc
0
0
prоvеrеnо 10.05.2024.
Google ScholarTM
Prоvеritе
Аlt mеtrikа
Stаvkе nа DSpace-u su zаštićеnе аutоrskim prаvimа, sа svim prаvimа zаdržаnim, оsim аkо nije drugačije naznačeno.