Asymptotically optimal approach for the maximum spanning tree problem with given diameter in a complete undirected graph on UNI(0;1)-entries
Автор: Gimadi Eduard Khairutdinovich, Shtepa Alexandr Alexandrovich
Журнал: Проблемы информатики @problem-info
Рубрика: Теоретическая и системная информатика
Статья в выпуске: 4 (57), 2022 года.
Бесплатный доступ
We consider two well-known optimization problems: the Minimum Spanning Tree Problem and the Maximum Spanning Tree Problem. There are some extensions of these problems, for example, if we want to find extremal spanning tree with bounded maximum degree of vertices or we search for extremal spanning tree with bounded diameter from above or from below by some integer. The diameter of a tree is the number of edges in the longest simple path within the tree connecting a pair of vertices. In current work, we consider the intractable problem of finding a maximum-weight spanning tree with a given diameter in a complete undirected graph. We construct O(n2)-time approximation algorithm solving the Maximum Spanning Tree Problem with a given diameter in a complete undirected n-vertex graph, and prove the sufficient conditions of asymptotic optimality for this algorithm in the case of independent uniformly distributed UNI(0; 1)-entries. This algorithm uses the algorithm for the Minimum Spanning Tree Problem with given diameter in a complete undirected graph.
Maximum spanning tree, minimum spanning tree, approximation algorithm, probabilistic analysis, asymptotic optimality
Короткий адрес: https://sciup.org/143179895
IDR: 143179895 | DOI: 10.24412/2073-0667-2022-4-53-62
Список литературы Asymptotically optimal approach for the maximum spanning tree problem with given diameter in a complete undirected graph on UNI(0;1)-entries
- 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. DOI: 10.1007/s00493-012-2552-z.
- 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. N 1. P. 89-107. DOI: 10.1017/S0963548315000024.
- Gimadi E. Kh., Istomin A. M., Shin E.Yu. On Algorithm for the Minimum Spanning Tree Problem Bounded Below // Proc. DOOR 2016, Vladivostok, Russia, 2016, CEUR-WS, V. 1623, P. 11-17.
- Gimadi E.Kh., Istomin A. M., Shin E.Yu. On Bounded Diameter MST Problem on Random Instances // CEUR Workshop Proceedings, 2019, P. 159-168.
- 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. (Inderfurth K. eds.), Springer, Berlin, 2000. V. 99. P. 63-68. DOI: 10.1007/978-3-642-58300-1_12.
- Gimadi E. Kh., Shevyakov A. S., Shin E.Yu. Asymptotically Optimal Approach to a Given Diameter Undirected MST Problem on Random Instances // Proceedings of 15th International Asian School-Seminar OPCS-2019, Publisher: IEEE Xplore, 2019, P. 48-52. DOI: 10.1109/OPCS.2019.8880223.
- 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.), the 11th International Conference - Optimization and Applications, OPTIMA 2020, LNCS, 2020. V. 12422. P. 110-121. DOI: 10.1007/978-3-030-62867-3_9.
- Gimadi E. Kh., Shevyakov A. S., Shtepa A.A. On Asymptotically Optimal Approach for the Problem of Finding Several Edge-Disjoint Spanning Trees of Given Diameter in an Undirected Graph with Random Edge Weights // In P. Pardalos, M. Khachay, A. Kazakov (eds.), Mathematical Optimization Theory and Operations Research, MOTOR 2021, LNCS, V. 12755, P. 67-78. DOI: 10.1007/978-3-030-77876-7_5.
- 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, 2019. V. 1090. Springer, Cham, P. 30-38. DOI: 10.1007/978-3-030-33394-2_3.
- Erzin A. I. The problem of constructing a spanning tree of maximal weight with a bounded radius // Upravlyaemye Sistemy, V. 27, 1987, P. 70-78. (in Russian).
- Serdyukov A. I. On problem of maximal spanning tree with bounded radius // Diskretn. Anal. Issled. Oper., Ser. 1, V. 5, N 3, 1998, P. 64-69. (in Russian).
- Garey M. R., Johnson D. S., Computers and Intractability. Freeman, San Francisco, 1979, 340 p.
- Gimadi E. Kh., Glebov N. I., Perepelitsa V. A. Algorithms with Estimates for Discrete Optimization Problems // Problemy Kibernetiki, V. 31, 1975, P. 35-42. (in Russian).
- Petrov V. V., Limit Theorems of Probability Theory. Sequences of Independent Random Variables. Clarendon Press, Oxford, 1995, 304 p.
- Gimadi E. Kh., Khachay M.Yu. Extremal Problems on Sets of Permutations. UrFU Publ. Ekaterinburg, 2016, 219 p. (in Russian).
