On Given Diameter MST Problem on Random Input Data

Edward Kh Gimadi, Ekaterina Yu Shin

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

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.

Original languageEnglish
Title of host publicationMathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers
EditorsIgor Bykadorov, Vitaly Strusevich, Tatiana Tchemisova
PublisherSpringer Gabler
Pages30-38
Number of pages9
ISBN (Print)9783030333935
DOIs
Publication statusPublished - 1 Jan 2019
Event18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 - Ekaterinburg, Russian Federation
Duration: 8 Jul 201912 Jul 2019

Publication series

NameCommunications in Computer and Information Science
Volume1090 CCIS
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Conference

Conference18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019
CountryRussian Federation
CityEkaterinburg
Period08.07.201912.07.2019

Keywords

  • Asymptotically optimal algorithm
  • Graph
  • Minimum spanning tree
  • Performance guarantees
  • Probabilistic analysis
  • Random inputs
  • Uniform

Fingerprint Dive into the research topics of 'On Given Diameter MST Problem on Random Input Data'. Together they form a unique fingerprint.

  • Cite this

    Gimadi, E. K., & Shin, E. Y. (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 (pp. 30-38). (Communications in Computer and Information Science; Vol. 1090 CCIS). Springer Gabler. https://doi.org/10.1007/978-3-030-33394-2_3