АСИМПТОТИЧЕСКИ ТОЧНЫЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧИ МАКСИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА С ФИКСИРОВАННЫМ ДИАМЕТРОМ В ПОЛНОМ НЕОРИЕНТИРОВАННОМ ГРАФЕ С ВХОДНЫМИ ДАННЫМИ ИЗ КЛАССА UNI(0; 1)

Авторы: 
Э.Х. Гимади*,** А. А. Штепа**
УДК: 
519.8
DOI: 
10.24412/2073-0667-2022-4-53-62
Аннотация: 

EDN: GMGWHI
Мы рассматриваем труднорешаемую задачу отыскания максимального остовного дерева с фиксированным диаметром в полном неориентированном графе. Для приближенного алгоритма с трудоемкостью O(n2), решающего эту задачу, где n — количество вершин в графе, мы доказываем достаточные условия асимптотической точности в случае весов ребер графа из класса независимых, равномерно распределенных случайных величин UNI(0; 1).

 

Работа выполнена в рамках государственного задания ИМ СО РАН (проект FWNF-2022-0019) и при финансовой поддержке РФФИ (проект 20-31-90091).

 

Ключевые слова: 
максимальное остовное дерево, минимальное остовное дерево, приближенный алгоритм, вероятностный анализ, асимптотическая точность.
Номер журнала: 
4(57) 2022 г.
Год: 
2022
Адрес: 
* Институт математики им. С. Л. Соболева СО РАН, 630090, Новосибирск, Россия, **Новосибирский государственный университет, 630090, Новосибирск, Россия
Библиографическая ссылка: 
Гимади Э. Х., Штепа А. А. Асимптотически точный подход к решению задачи максимального остовного дерева с фиксированным диаметром в полном неориентированном графе с входными данными из класса UNI$(0;1) //Проблемы информатики. 2022. № 4. С. 53–62. DOI: 10.24412/2073-0667-2022-4-53-62. EDN: GMGWHI