@inproceedings{3a85b01ad0ee47d9bbe1679d62b6d5b3,

title = "Asymptotically Optimal Approach to a Given Diameter Undirected MST Problem on Random Input Data",

abstract = "We give an approximation deterministic algorithm for solving the Random Undirected MST with given diameter on n-vertex complete undirected 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 approach, minimum spanning tree, performance guarantees, probabilistic analysis, random inputs, undirected graph, uniform",

author = "Edward Gimadi and Alexandr Shevyakov and Ekaterina Shin",

note = "Funding Information: Supported by the program of fundamental scientific researches of the SB RAS (project 0314-2019-0014), by RFBR (project 20-01-00583), and by the Ministry of Science and Higher Education of the Russian Federation under the 5-100 Excellence Programme.; 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 ; Conference date: 26-08-2019 Through 30-08-2019",

year = "2019",

month = aug,

doi = "10.1109/OPCS.2019.8880223",

language = "English",

series = "2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "48--52",

booktitle = "2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019",

address = "United States",

}