A Given Diameter MST on a Random Graph

Edward K. Gimadi, Aleksandr S. Shevyakov, Alexandr A. Shtepa

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

We give a new approximation polynomial time algorithm for one of the intractable problem of finding given-diameter Minimum Spanning Tree (MST) on n-vertex complete graph with randomly weighted edges. A significant advantage of this algorithm is that it turned out to be well suited for finding several edge-disjoint MST of a given diameter. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an segment. Sufficient conditions of asymptotic optimality are presented. It is also noteworthy that the new algorithmic approach to solve the problem of finding a given-diameter MST both on directed and undirected graphs.

Язык оригиналаанглийский
Название основной публикацииOptimization and Applications - 11th International Conference, OPTIMA 2020, Proceedings
РедакторыNicholas Olenev, Yuri Evtushenko, Michael Khachay, Vlasta Malkova
ИздательSpringer Science and Business Media Deutschland GmbH
Страницы110-121
Число страниц12
ISBN (печатное издание)9783030628666
DOI
СостояниеОпубликовано - 2020
Событие11th International Conference on Optimization and Applications, OPTIMA 2020 - Moscow, Российская Федерация
Продолжительность: 28 сен 20202 окт 2020

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том12422 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция11th International Conference on Optimization and Applications, OPTIMA 2020
СтранаРоссийская Федерация
ГородMoscow
Период28.09.202002.10.2020

Fingerprint Подробные сведения о темах исследования «A Given Diameter MST on a Random Graph». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать