Standard
A Given Diameter MST on a Random Graph. / Gimadi, Edward K.; Shevyakov, Aleksandr S.; Shtepa, Alexandr A.
Optimization and Applications - 11th International Conference, OPTIMA 2020, Proceedings. ed. / Nicholas Olenev; Yuri Evtushenko; Michael Khachay; Vlasta Malkova. Springer Science and Business Media Deutschland GmbH, 2020. p. 110-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12422 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Gimadi, EK, Shevyakov, AS & Shtepa, AA 2020,
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, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12422 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 110-121, 11th International Conference on Optimization and Applications, OPTIMA 2020, Moscow, Russian Federation,
28.09.2020.
https://doi.org/10.1007/978-3-030-62867-3_9
APA
Gimadi, E. K., Shevyakov, A. S., & Shtepa, A. A. (2020).
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, Proceedings (pp. 110-121). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12422 LNCS). Springer Science and Business Media Deutschland GmbH.
https://doi.org/10.1007/978-3-030-62867-3_9
Vancouver
Gimadi EK, Shevyakov AS, Shtepa AA.
A Given Diameter MST on a Random Graph. In Olenev N, Evtushenko Y, Khachay M, Malkova V, editors, Optimization and Applications - 11th International Conference, OPTIMA 2020, Proceedings. Springer Science and Business Media Deutschland GmbH. 2020. p. 110-121. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-62867-3_9
Author
Gimadi, Edward K. ; Shevyakov, Aleksandr S. ; Shtepa, Alexandr A. /
A Given Diameter MST on a Random Graph. Optimization and Applications - 11th International Conference, OPTIMA 2020, Proceedings. editor / Nicholas Olenev ; Yuri Evtushenko ; Michael Khachay ; Vlasta Malkova. Springer Science and Business Media Deutschland GmbH, 2020. pp. 110-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{ada220e41da548caa247dd800013ce5c,
title = "A Given Diameter MST on a Random Graph",
abstract = "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.",
keywords = "Approximation algorithm, Given-diameter minimum spanning tree, Probabilistic analysis",
author = "Gimadi, {Edward K.} and Shevyakov, {Aleksandr S.} and Shtepa, {Alexandr A.}",
note = "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: {\textcopyright} 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 11th International Conference on Optimization and Applications, OPTIMA 2020 ; Conference date: 28-09-2020 Through 02-10-2020",
year = "2020",
doi = "10.1007/978-3-030-62867-3_9",
language = "English",
isbn = "9783030628666",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "110--121",
editor = "Nicholas Olenev and Yuri Evtushenko and Michael Khachay and Vlasta Malkova",
booktitle = "Optimization and Applications - 11th International Conference, OPTIMA 2020, Proceedings",
address = "Germany",
}
RIS
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 -
