- PII
- 10.31857/S0005231023070085-1
- DOI
- 10.31857/S0005231023070085
- Publication type
- Article
- Status
- Published
- Authors
- Volume/ Edition
- Volume / Issue number 7
- Pages
- 146-166
- Abstract
- We consider the intractable problem of finding several edge-disjoint spanning trees of the minimum total weight with a given diameter in complete undirected graph in current paper. The weights of edges of a graph are random variables from several continuous distributions: uniform, biased truncated exponential, biased truncated normal. The approximation algorithm with time complexity O(n2), where n is number of vertices in graph, is proposed for solving this problem. The asymptotic optimality conditions for constructed algorithm is presented for each considered probabilistic distribution.
- Keywords
- минимальное остовное дерево с ограниченным диаметром приближенный алгоритм вероятностный анализ асимптотическая точность
- Date of publication
- 15.07.2023
- Year of publication
- 2023
- Number of purchasers
- 0
- Views
- 3
References
- 1. Frieze A. On the Value of a Random MST Problem // Discrete Applied Mathematics. 1985. V. 10. P. 47-56. https://doi.org/10.1016/0166-218X (85)90058-7
- 2. Angel O., Flaxman A.D., Wilson D.B. A Sharp Threshold for Minimum Bounded-Depth and Bounded-Diameter Spanning Trees and Steiner Trees in Random Networks // Combinatorica. 2012. V. 32. P. 1-33. https://doi.org/10.1007/s00493-012-2552-z
- 3. Cooper C., Frieze A., Ince N., Janson S., Spencer J. On the Length of a Random Minimum Spanning Tree // Combinatorics, Probability and Computing. 2016. V. 25. No. 1. P. 89-107. https://doi.org/10.1017/S0963548315000024
- 4. Garey M.R., Johnson D.S. Computers and Intractability. 1979. Freeman, San Francisco. 340 p.
- 5. Clementi A.E.F., Ianni M.D., Monti A., Rossi, G., Silvestri R. Experimental Analysis of Practically E cient Algorithms for Bounded-Hop Accumulation in Ad-Hoc Wireless Networks // Proc. 19th IEEE Int. Parallel Distributed Processing Symposium (IPDPS'05). 2005. P. 8-16. https://doi.org/10.1109/IPDPS.2005.210
- 6. Bala K., Petropoulos K., Stern T.E. Multicasting in a Linear Lightwave Network // Proc. of IEEE INFOCOM'93. 1993. P. 1350-1358. https://doi.org/10.1109/INFCOM.1993.253399
- 7. Bookstein A., Klein S.T. Compression of Correlated Bit-Vectors // Inform. Syst. 1996. V. 16. No. 4. P. 110-118.
- 8. Raymond K. A Tree-Based Algorithm for Distributed Mutual Exclusion // ACM Trans. on Comput. Syst. 1989. V. 7. No. 1. P. 61-77. https://doi.org/10.1145/58564.59295
- 9. Gruber M. Exact and Heuristic Approaches for Solving the Bounded Diameter Minimum Spanning Tree Problem. Vienna University of Technology. PhD Thesis. 2009.
- 10. Gimadi E.Kh., Serdyukov A.I. A Probabilistic Analysis of Approximation Algorithm for the Minimum Weight Spanning Tree Problem with a Bounded Below Diameter / Oper. Res. Proceed. V. 99. In: K. Inderfurth et. al. (eds.). Springer, Berlin. 2000. P. 63-68. https://doi.org/10.1007/978-3-642-58300-1_12
- 11. Gimadi E.Kh., Istomin A.M., Shin E.Yu. On Algorithm for the Minimum Spanning Tree Problem Bounded Below // Proc. conference DOOR 2016. Vladivostok. Russia. CEUR-WS. V. 1623. 2016. P. 11-17.
- 12. Gimadi E.Kh., Shin E.Yu. On Given Diameter MST Problem on Random Input Data / In: I. Bykadorov, V. Strusevich, T. Tchemisova (eds.). MOTOR 2019. Communications in Computer and Information Science. V. 1090. Springer, Cham. 2019. P. 30-38. https://doi.org/10.1007/978-3-030-33394-2_3
- 13. Gimadi E.Kh., Shevyakov A.S., Shtepa A.A. A Given Diameter MST on a Random Graph / In: N. Olenev, Y. Evtushenko, M. Khachay, V. Malkova (eds.). Optimization and Applications - 11th International Conference OPTIMA. 2020. LNCS. V. 12422. P. 110-121. https://doi.org/10.1007/978-3-030-62867-3_9
- 14. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. 1975. Вып. 31. С. 35-42.
- 15. Petrov V.V. Limit Theorems of Probability Theory. Sequences of Independent Random Variables. 1995. Clarendon Press. Oxford. 304 p.
- 16. Гимади Э.Х., Глазков Ю.В. Об асимптотически точном алгоритме решения одной модификации трехиндексной планарной задачи о назначениях // Дискретный анализ и исследование операций. 2006. Сер. 2. Т. 13. № 1. С. 10-26.
- 17. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: Изд-во УМЦ УПИ, 2016. 219 c.
- 18. Гимади Э.Х., Шин Е.Ю. Вероятностный анализ алгоритма нахождения в графе минимального остовного дерева с ограниченным снизу диаметром // Дискретный анализ и исследование операций. 2015. Т. 22. № 4. С. 5-20. https://doi.org/10.17377/daio.2015.22.474
