Аннотация
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.
Язык оригинала | английский |
---|---|
Страницы (с-по) | 159-168 |
Число страниц | 10 |
Журнал | CEUR Workshop Proceedings |
Том | 2098 |
Состояние | Опубликовано - 1 янв 2018 |
Событие | 2018 School-Seminar on Optimization Problems and their Applications, OPTA-SCL 2018 - Omsk, Российская Федерация Продолжительность: 8 июл 2018 → 14 июл 2018 |