On Asymptotically Optimal Approach for the Problem of Finding Several Edge-Disjoint Spanning Trees of Given Diameter in an Undirected Graph with Random Edge Weights

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

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

Аннотация

We consider the intractable problem of finding several edge-disjoint spanning trees of a given diameter in an graph with random edge weights. Earlier, we have implemented an asymptotically optimal approach for this problem in the case of directed graphs. The direct use of this result for the case of undirected graphs turned out to be impossible due to the issues associated with the summation of dependent random variables. In this work we give an O(n2) -time algorithm with conditions of asymptotic optimality for the case of undirected graphs.

Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings
РедакторыPanos Pardalos, Michael Khachay, Alexander Kazakov
ИздательSpringer Science and Business Media Deutschland GmbH
Страницы67-78
Число страниц12
ISBN (печатное издание)9783030778750
DOI
СостояниеОпубликовано - 2021
Событие20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021 - Irkutsk, Российская Федерация
Продолжительность: 5 июл 202110 июл 2021

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

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

Конференция

Конференция20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021
СтранаРоссийская Федерация
ГородIrkutsk
Период05.07.202110.07.2021

Предметные области OECD FOS+WOS

  • 1.01 МАТЕМАТИКА
  • 1.02 КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ

Fingerprint

Подробные сведения о темах исследования «On Asymptotically Optimal Approach for the Problem of Finding Several Edge-Disjoint Spanning Trees of Given Diameter in an Undirected Graph with Random Edge Weights». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать