Асимптотически точный подход к решению задачи максимального остовного дерева с фиксированным диаметром в полном неориентированном графе с входными данными из класса UNI(0; 1)
Автор: Гимади Эдуард Хайрутдинович, Штепа Александр Александрович
Журнал: Проблемы информатики @problem-info
Рубрика: Теоретическая и системная информатика
Статья в выпуске: 4 (57), 2022 года.
Бесплатный доступ
Мы рассматриваем труднорешаемую задачу отыскания максимального остовного дерева с фиксированным диаметром в полном неориентированном графе. Для приближенного алгоритма с трудоемкостью O(n2), решающего эту задачу, где n - количество вершин в графе, мы доказываем достаточные условия асимптотической точности в случае весов ребер графа из класса независимых, равномерно распределенных случайных величин UNI(0; 1).
Максимальное остовнос дерево, минимальное остовнос дерево, приближенный алгоритм, вероятностный анализ, асимптотическая точность
Короткий адрес: https://sciup.org/143179895
IDR: 143179895 | DOI: 10.24412/2073-0667-2022-4-53-62
