Asymptotically Optimal Approach to a Given Diameter Undirected MST Problem on Random Input Data

Edward Gimadi, Alexandr Shevyakov, Ekaterina Shin

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

1 Citation (Scopus)

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.

Original languageEnglish
Title of host publication2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages48-52
Number of pages5
ISBN (Electronic)9781728129860
DOIs
Publication statusPublished - Aug 2019
Event15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 - Novosibirsk, Russian Federation
Duration: 26 Aug 201930 Aug 2019

Publication series

Name2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019

Conference

Conference15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
CountryRussian Federation
CityNovosibirsk
Period26.08.201930.08.2019

Keywords

  • asymptotically optimal approach
  • minimum spanning tree
  • performance guarantees
  • probabilistic analysis
  • random inputs
  • undirected graph
  • uniform

Fingerprint Dive into the research topics of 'Asymptotically Optimal Approach to a Given Diameter Undirected MST Problem on Random Input Data'. Together they form a unique fingerprint.

Cite this