Асимптотически точный подход к решению задачи максимального остовного дерева с фиксированным диаметром в полном неориентированном графе с входными данными из класса UNI(0; 1)

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