|
This article is cited in 7 scientific papers (total in 7 papers)
Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded from below
E. Kh. Gimadiab, E. Yu. Shinb a Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia
b Sobolev Institute of Mathematics, 4 Koptyug Ave., 630090 Novosibirsk, Russia
Abstract:
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.
Keywords:
spanning tree, polynomial algorithm, the probabilistic analysis, performance guarantee, asymptotic optimality.
Received: 10.02.2015 Revised: 04.05.2015
Citation:
E. Kh. Gimadi, E. Yu. Shin, “Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded from below”, Diskretn. Anal. Issled. Oper., 22:4 (2015), 5–20; J. Appl. Industr. Math., 9:4 (2015), 480–488
Linking options:
https://www.mathnet.ru/eng/da821 https://www.mathnet.ru/eng/da/v22/i4/p5
|
Statistics & downloads: |
Abstract page: | 322 | Full-text PDF : | 103 | References: | 37 | First page: | 14 |
|