Volume 22, No 4, 2015, P. 5-20

UDC 519.8
Gimadi E. Kh., Shin E. Yu.
Probabilistic analysis of an algorithm for the minimal spanning tree problem with diameter bounded from below

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.

DOI: 10.17377/daio.2015.22.474

Edward Kh. Gimadi ^1,2
Ekaterina Yu. Shin ¹
1. Sobolev Institute of Mathematics
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: gimadi@math.nsc.ru, Shinus90@yandex.ru

Received 10 February 2015
Revised 4 May 2015

References

[1] E. Kh. Gimadi and Yu. V. Glazkov, An asymptotically optimal algorithm for one modification of planar three-index assignment problem, Diskretn. Anal. Issled. Oper., Ser. 2, 13, No. 1, 10–26, 2006. Translated in J. Appl. Ind. Math., 1, No. 4, 442–452, 2007.

[2] E. Kh. Gimadi, A. Le Gallou, and A. V. Shakhshneyder, Probabilistic analysis of an approximation algorithm for the traveling salesman problem on unbounded above instances, Diskretn. Anal. Issled. Oper., 15, No. 1, 23–43, 2008. Translated in J. Appl. Ind. Math., 3, No. 2, 207–221, 2009.

[3] E. Kh. Gimadi and V. A. Perepelitsa, An asymptotic approach to the traveling salesman problem, in Upravlyaemye sistemy (Controlled Systems), Vol. 12, pp. 35–45, Inst. Mat. SO AN SSSR, Novosibirsk, 1974.

[4] E. Kh. Gimadi and A. I. Serdyukov, An algorithm for finding the minimum spanning tree with a diameter bounded from below, Diskretn. Anal. Issled. Oper., Ser. 1, 7, No. 2, 3–11, 2000.

[5] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Mir, Moscow, 1982.

[6] V. A. Perepelitsa and E. Kh. Gimadi, The minimum Hamiltonian cycle problem in a weighted graph, in Diskretnyi analiz (Discrete Analysis), Vol. 15, pp. 57–65, Inst. Mat. SO AN SSSR, Novosibirsk, 1969.

[7] V. V. Petrov, Predelnye teoremy dlya summ nezavisimykh sluchainykh velichin (Limit Theorems for Sums of Independent Random Variables), Nauka, Moscow, 1987.

[8] R. C. Prim, Shortest connection networks and some generalizations, Bell Syst. Techn. J., 36, No. 6, 1389–1401, 1957. Translated in Kiberneticheskii sbornik (Cybernetic Sbornik), Vol. 2, pp. 95–107, Mir, Moscow, 1961.

[9] A. Abdalla, N. Deo, and P. Gupta, Random-tree diameter and the diameter-constrained MST, Congr. Numerantium, 144, 161–182, 2000.

[10] D. J. Bertsimas, The probabilistic minimum spanning tree problem, Networks, 20, No. 3, 245–275, 1990.

[11] M. Gruber and G. R. Raidl, A new 0–1 ILP approach for the bounded-diameter minimum spanning tree problem, in L. Gouveia and C. Mourao, eds., Proc. 2nd Int. Netw. Optim. Conf., Lisbon, Portugal, Mar. 20–23, 2005, Vol. 1, pp. 178–185, 2005.

[12] D. S. Johnson, J. K. Lenstra, and A. H. G. Rinnooy Kan, The complexity of the network design problem, Networks, 8, No. 4, 279–285, 1978.

[13] B. A. Julstrom, Greedy heuristics for the bounded-diameter minimum spanning tree problem, J. Exp. Algorithmics, 14, 1–14, 2009.

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

[15] K. Ozeki and T. Yamashita, Spanning trees: A survey, Graphs Comb., 27, No. 1, 1–26, 2011.

[16] G. R. Raidl and B. A. Julstrom, Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem, in Proc. 2003 ACM Symp. Appl. Comput., Melbourne, FL, USA, Mar. 9–12, 2003, pp. 747–752, ACM, New York, 2003.

[17] R. Jothi and B. Raghavachari, Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design, ACM Trans. Algorithms, 1, No. 2, 265–282, 2005.