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 language | English |
---|---|
Pages (from-to) | 159-168 |
Number of pages | 10 |
Journal | CEUR Workshop Proceedings |
Volume | 2098 |
Publication status | Published - 1 Jan 2018 |
Event | 2018 School-Seminar on Optimization Problems and their Applications, OPTA-SCL 2018 - Omsk, Russian Federation Duration: 8 Jul 2018 → 14 Jul 2018 |
Keywords
- Asymptotically optimal algorithm
- Bounded diameter minimum spanning tree
- Graph
- Minimum spanning tree
- Performance guarantees
- Probabilistic analysis
- Random inputs
- Uniform