On bounded diameter MST problem on random instances

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

Результат исследования: Научные публикации в периодических изданияхстатья по материалам конференции

1 Цитирования (Scopus)

Аннотация

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 июл 201814 июл 2018

Fingerprint Подробные сведения о темах исследования «On bounded diameter MST problem on random instances». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать