@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",

}