Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded from below

Graphs with distance matrices are considered with weights of edges being independent random variables distributed on the interval unbounded from above. Probabilistic analysis of a polynomial algorithm is performed. In the cases of exponential and truncated normal distribution, conditions for asymptotic optimality are presented. Ill. 2, bibliogr. 17.