Asymptotically Optimal Approach to a Given Diameter Undirected MST Problem on Random Input Data

Edward Gimadi, Alexandr Shevyakov, Ekaterina Shin

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

Аннотация

We give an approximation deterministic algorithm for solving the Random Undirected MST with given diameter on n-vertex complete undirected graph. The problem is NP-hard. 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 with positive ends. Sufficient conditions of asymptotic optimality are presented.

Язык оригиналаанглийский
Название основной публикации2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
ИздательInstitute of Electrical and Electronics Engineers Inc.
Страницы48-52
Число страниц5
ISBN (электронное издание)9781728129860
DOI
СостояниеОпубликовано - авг 2019
Опубликовано для внешнего пользованияДа
Событие15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 - Novosibirsk, Российская Федерация
Продолжительность: 26 авг 201930 авг 2019

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

Название2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019

Конференция

Конференция15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
СтранаРоссийская Федерация
ГородNovosibirsk
Период26.08.201930.08.2019

Fingerprint Подробные сведения о темах исследования «Asymptotically Optimal Approach to a Given Diameter Undirected MST Problem on Random Input Data». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Gimadi, E., Shevyakov, A., & Shin, E. (2019). Asymptotically Optimal Approach to a Given Diameter Undirected MST Problem on Random Input Data. В 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 (стр. 48-52). [8880223] (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/OPCS.2019.8880223