A Given Diameter MST on a Random Graph

Edward K. Gimadi, Aleksandr S. Shevyakov, Alexandr A. Shtepa

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review


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.

Original languageEnglish
Title of host publicationOptimization and Applications - 11th International Conference, OPTIMA 2020, Proceedings
EditorsNicholas Olenev, Yuri Evtushenko, Michael Khachay, Vlasta Malkova
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages12
ISBN (Print)9783030628666
Publication statusPublished - 2020
Event11th International Conference on Optimization and Applications, OPTIMA 2020 - Moscow, Russian Federation
Duration: 28 Sep 20202 Oct 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12422 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference11th International Conference on Optimization and Applications, OPTIMA 2020
CountryRussian Federation


  • Approximation algorithm
  • Given-diameter minimum spanning tree
  • Probabilistic analysis


Dive into the research topics of 'A Given Diameter MST on a Random Graph'. Together they form a unique fingerprint.

Cite this