TY - GEN
T1 - A Given Diameter MST on a Random Graph
AU - Gimadi, Edward K.
AU - Shevyakov, Aleksandr S.
AU - Shtepa, Alexandr A.
N1 - Funding Information:
Supported by the program of fundamental scientific researches of the SB RAS No. I.5.1., project No. 0314-2019-0014, and by the Russian Foundation for Basic Research, project No. 20-31-90091.
Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020
Y1 - 2020
N2 - We give a new approximation polynomial time algorithm for one of the intractable problem of finding given-diameter Minimum Spanning Tree (MST) on n-vertex complete graph with randomly weighted edges. A significant advantage of this algorithm is that it turned out to be well suited for finding several edge-disjoint MST of a given diameter. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an segment. Sufficient conditions of asymptotic optimality are presented. It is also noteworthy that the new algorithmic approach to solve the problem of finding a given-diameter MST both on directed and undirected graphs.
AB - We give a new approximation polynomial time algorithm for one of the intractable problem of finding given-diameter Minimum Spanning Tree (MST) on n-vertex complete graph with randomly weighted edges. A significant advantage of this algorithm is that it turned out to be well suited for finding several edge-disjoint MST of a given diameter. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an segment. Sufficient conditions of asymptotic optimality are presented. It is also noteworthy that the new algorithmic approach to solve the problem of finding a given-diameter MST both on directed and undirected graphs.
KW - Approximation algorithm
KW - Given-diameter minimum spanning tree
KW - Probabilistic analysis
UR - http://www.scopus.com/inward/record.url?scp=85097423231&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-62867-3_9
DO - 10.1007/978-3-030-62867-3_9
M3 - Conference contribution
AN - SCOPUS:85097423231
SN - 9783030628666
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 110
EP - 121
BT - Optimization and Applications - 11th International Conference, OPTIMA 2020, Proceedings
A2 - Olenev, Nicholas
A2 - Evtushenko, Yuri
A2 - Khachay, Michael
A2 - Malkova, Vlasta
PB - Springer Science and Business Media Deutschland GmbH
T2 - 11th International Conference on Optimization and Applications, OPTIMA 2020
Y2 - 28 September 2020 through 2 October 2020
ER -