Standard
On Given Diameter MST Problem on Random Input Data. / Gimadi, Edward Kh; Shin, Ekaterina Yu.
Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. ed. / Igor Bykadorov; Vitaly Strusevich; Tatiana Tchemisova. Springer Gabler, 2019. p. 30-38 (Communications in Computer and Information Science; Vol. 1090 CCIS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Gimadi, EK & Shin, EY 2019,
On Given Diameter MST Problem on Random Input Data. in I Bykadorov, V Strusevich & T Tchemisova (eds),
Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. Communications in Computer and Information Science, vol. 1090 CCIS, Springer Gabler, pp. 30-38, 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019, Ekaterinburg, Russian Federation,
08.07.2019.
https://doi.org/10.1007/978-3-030-33394-2_3
APA
Vancouver
Gimadi EK, Shin EY.
On Given Diameter MST Problem on Random Input Data. In Bykadorov I, Strusevich V, Tchemisova T, editors, Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. Springer Gabler. 2019. p. 30-38. (Communications in Computer and Information Science). doi: 10.1007/978-3-030-33394-2_3
Author
Gimadi, Edward Kh ; Shin, Ekaterina Yu. /
On Given Diameter MST Problem on Random Input Data. Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. editor / Igor Bykadorov ; Vitaly Strusevich ; Tatiana Tchemisova. Springer Gabler, 2019. pp. 30-38 (Communications in Computer and Information Science).
BibTeX
@inproceedings{6662222e38a44d099089ef1a5772ee7d,
title = "On Given Diameter MST Problem on Random Input Data",
abstract = "We give an approximation deterministic algorithm for solving the Random MST with given diameter of directed graph. The problem is NP-hard. Algorithm has a quadratic time complexity. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an interval with positive ends. Sufficient conditions of asymptotic optimality are presented.",
keywords = "Asymptotically optimal algorithm, Graph, Minimum spanning tree, Performance guarantees, Probabilistic analysis, Random inputs, Uniform",
author = "Gimadi, {Edward Kh} and Shin, {Ekaterina Yu}",
note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG. Copyright: Copyright 2019 Elsevier B.V., All rights reserved.; 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 ; Conference date: 08-07-2019 Through 12-07-2019",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-33394-2_3",
language = "English",
isbn = "9783030333935",
series = "Communications in Computer and Information Science",
publisher = "Springer Gabler",
pages = "30--38",
editor = "Igor Bykadorov and Vitaly Strusevich and Tatiana Tchemisova",
booktitle = "Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers",
address = "Germany",
}
RIS
TY - GEN
T1 - On Given Diameter MST Problem on Random Input Data
AU - Gimadi, Edward Kh
AU - Shin, Ekaterina Yu
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - We give an approximation deterministic algorithm for solving the Random MST with given diameter of directed graph. The problem is NP-hard. Algorithm has a quadratic time complexity. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an interval with positive ends. Sufficient conditions of asymptotic optimality are presented.
AB - We give an approximation deterministic algorithm for solving the Random MST with given diameter of directed graph. The problem is NP-hard. Algorithm has a quadratic time complexity. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an interval with positive ends. Sufficient conditions of asymptotic optimality are presented.
KW - Asymptotically optimal algorithm
KW - Graph
KW - Minimum spanning tree
KW - Performance guarantees
KW - Probabilistic analysis
KW - Random inputs
KW - Uniform
UR - http://www.scopus.com/inward/record.url?scp=85076188447&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-33394-2_3
DO - 10.1007/978-3-030-33394-2_3
M3 - Conference contribution
AN - SCOPUS:85076188447
SN - 9783030333935
T3 - Communications in Computer and Information Science
SP - 30
EP - 38
BT - Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers
A2 - Bykadorov, Igor
A2 - Strusevich, Vitaly
A2 - Tchemisova, Tatiana
PB - Springer Gabler
T2 - 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019
Y2 - 8 July 2019 through 12 July 2019
ER -
