On bounded diameter MST problem on random instances

Edward Kh Gimadi, Alexey M. Istomin, Ekaterina Yu Shin

Research output: Contribution to journalConference articlepeer-review

1 Citation (Scopus)

Abstract

We give an approximation deterministic algorithm for solving the Random bounded diameter minimum spanning tree (BDMST) problem on an undirected graph. The 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 (an;bn). Conditions of asymptotic optimality are presented.

Original languageEnglish
Pages (from-to)159-168
Number of pages10
JournalCEUR Workshop Proceedings
Volume2098
Publication statusPublished - 1 Jan 2018
Event2018 School-Seminar on Optimization Problems and their Applications, OPTA-SCL 2018 - Omsk, Russian Federation
Duration: 8 Jul 201814 Jul 2018

Keywords

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

Fingerprint Dive into the research topics of 'On bounded diameter MST problem on random instances'. Together they form a unique fingerprint.

Cite this