Geodesic
Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded from below
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 4, pp. 5-20

Voir la notice de l'article provenant de la source Math-Net.Ru

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, the probabilistic analysis, performance guarantee, asymptotic optimality.
Mots-clés : polynomial algorithm 
@article{DA_2015_22_4_a0,
     author = {E. Kh. Gimadi and E. Yu. Shin},
     title = {Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded from below},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--20},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_4_a0/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - E. Yu. Shin
TI  - Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded from below
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 5
EP  - 20
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_4_a0/
LA  - ru
ID  - DA_2015_22_4_a0
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A E. Yu. Shin
%T Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded from below
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 5-20
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_4_a0/
%G ru
%F DA_2015_22_4_a0
E. Kh. Gimadi; E. Yu. Shin. Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded from below. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 4, pp. 5-20. http://geodesic.mathdoc.fr/item/DA_2015_22_4_a0/