Classification en composantes connexes, cas particulier de l’ultramétrique inférieure maximale : un algorithme O(n) en temps moyen
Revue de Statistique Appliquée, Volume 40 (1992) no. 3, p. 63-72
@article{RSA_1992__40_3_63_0,
     author = {Lehert, Ph.},
     title = {Classification en composantes connexes, cas particulier de l'ultram\'etrique inf\'erieure maximale : un algorithme $O(n)$ en temps moyen},
     journal = {Revue de Statistique Appliqu\'ee},
     publisher = {Soci\'et\'e de Statistique de France},
     volume = {40},
     number = {3},
     year = {1992},
     pages = {63-72},
     language = {fr},
     url = {http://www.numdam.org/item/RSA_1992__40_3_63_0}
}
Lehert, Ph. Classification en composantes connexes, cas particulier de l’ultramétrique inférieure maximale : un algorithme $O(n)$ en temps moyen. Revue de Statistique Appliquée, Volume 40 (1992) no. 3, pp. 63-72. http://www.numdam.org/item/RSA_1992__40_3_63_0/

[1] Levinthal C. Molecular model building by computer, Scientific american, 214, pp. 42-52, (1966).

[2] Rosenfeld A. Picture Processing by computer, Academic Press, New York, (1969). | Zbl 0198.52401

[3] Gower J.C., Ross J.S. Minimum Spanning tree and Single Linkage Clustering Analysis, Applied Statictics, 18, pp. 54-64, (1969). | MR 242315

[4] Bentley J., Stanat D. and Williams E.H. The complexity of finding fixed radius near neighbours, Inf. Proc. letters, 6.6, pp. 209-213, (1977). | MR 489084 | Zbl 0373.68041

[5] Bentley J. Friedmann J.M. Fast Algorithms for constructing minimum spanning trees in coordinate spaces, I.E.E.E. Trans. on computers, Vol. C-27, pp. 97-104, (1978). | Zbl 0369.68027

[6] Lehert Ph. Clustering by Connected Components in O(n) expected time, R.A.I.R.O Computer Science, 28, (1981). | MR 637563 | Zbl 0468.68079

[7] Anderberg M.R. Cluster Analysis for Applications, New York, Academic Press, (1973). | MR 326934 | Zbl 0299.62029

[8] Lehert Ph., Ultramétrique inférieure maximale et Complexité, Data Analysis and Informatics, Diday Ed., North Holland, (1985).

[9] Hammersley J.M. On rate of convergence to the connective constant of the hypercubical lattice, Quart. J .math. 2-12, p. 250-256 (1961). | MR 137660 | Zbl 0122.36404

[10] Santalo L.A. Integral Geometry and Geometric probability, Encyclopedia of Mathematics and its applications, v. 1. Addison Wesley, Reading, MA. (1976). | MR 433364 | Zbl 0342.53049

[11] Day W.H.E. Efficient algorithms for agglomerative hierarchical clustering methods, J. of Classification, 1, 7- 24, 1984. | Zbl 0563.62034

[12] Karchaf I. Sur la complexité des algorithmes de classification ascendante hiérarchique, Les cahiers de l'analyse des données, XII, 195-197, 1987.

[13] Rohlf F.J. A probabilistic Minimum Spanning Tree Algorithm, Information Processing Letters, 7, 44-48 (1978). | MR 461980 | Zbl 0365.68027

[14] Reh W., First Passage Percolation under weak moment conditions, J. App. Prob, 16, 750-763, (1979). | MR 549555 | Zbl 0428.60099