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/

[1] E. Kh. Gimadi, Yu. V. Glazkov, “An asymptotically optimal algorithm for one modification of planar three-index assignment problem”, J. Appl. Ind. Math., 1:4 (2007), 442–452 | DOI | MR | Zbl

[2] E. Kh. Gimadi, A. Le Gallou, A. V. Shakhshneyder, “Probabilistic analysis of an approximation algorithm for the traveling salesman problem on unbounded above instances”, J. Appl. Ind. Math., 3:2 (2009), 207–221 | DOI | MR | Zbl

[3] E. Kh. Gimadi, V. A. Perepelitsa, “An asymptotic approach to the traveling salesman problem”, Controlled Systems, 12, Inst. Mat. SO AN SSSR, Novosibirsk, 1974, 35–45 | Zbl

[4] E. Kh. Gimadi, A. I. Serdyukov, “An algorithm for finding the minimum spanning tree with a diameter bounded from below”, Diskretn. Anal. Issled. Oper., Ser. 1, 7:2 (2000), 3–11 | MR | Zbl

[5] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | MR | Zbl

[6] V. A. Perepelitsa, E. Kh. Gimadi, “The minimum Hamiltonian cycle problem in a weighted graph”, Discrete Analysis, 15, Inst. Mat. SO AN SSSR, Novosibirsk, 1969, 57–65 | MR

[7] V. V. Petrov, Limit Theorems for Sums of Independent Random Variables, Nauka, Moscow, 1987 | MR

[8] R. C. Prim, “Shortest connection networks and some generalizations”, Bell Syst. Techn. J., 36:6 (1957), 1389–1401 | DOI

[9] Abdalla A., Deo N., Gupta P., “Random-tree diameter and the diameter constrained MST”, Congr. Numerantium, 144 (2000), 161–182 | MR | Zbl

[10] Bertsimas D. J., “The probabilistic minimum spanning tree problem”, Networks, 20:3 (1990), 245–275 | DOI | MR | Zbl

[11] Gruber M., Raidl G. R., “A new 0-1 ILP approach for the bounded-diameter minimum spanning tree problem”, Proc. 2nd Int. Network Optimization Conf. (Lisbon, Portugal, March 20–23, 2005), v. 1, 2005, 178–185

[12] Johnson D. S., Lenstra J. K., Rinnooy Kan A. H. G., “The complexity of the network design problem”, Networks, 8:4 (1978), 279–285 | DOI | MR | Zbl

[13] Julstrom B. A., “Greedy heuristics for the bounded-diameter minimum spanning tree problem”, J. Exp. Algorithmics, 14 (2009), 1–14 | DOI | MR | Zbl

[14] Julstrom B. A., Raidl G. R., “A permutation-coded evolutionary algorithm for the bounded-diameter minimum spanning tree problem”, Genet. Evol. Comput. Conference's Workshops Proc., Workshop Anal. Des. Represent. Operat. (Chicago, USA, July 12–16, 2003), 2003, 2–7, Accessed June 11, 2015 Available at https://www.ac.tuwien.ac.at/files/pub/julstrom-03.pdf

[15] Ozeki K., Yamashita T., “Spanning trees: A survey”, Graphs Comb., 27:1 (2011), 1–26 | DOI | MR | Zbl

[16] Raidl G. R., Julstrom B. A., “Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem”, Proc. 2003 ACM Symp. Applied Computing (Melbourne, FL, March 9–12, 2003), ACM Press, New York, 2003, 747–752 | DOI

[17] Jothi R., Raghavachari B., “Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design”, ACM Trans. Algorithms, 1:2 (2005), 265–282 | DOI | MR