Приближенный алгоритм поиска $d$-однородного связного остовного подграфа максимального веса в полном графе со случайными весами ребер

Предложен приближeнный полиномиальный алгоритм для решения задачи поиска $d$-однородного связного остовного подграфа максимального веса в полном неориентированном взвешенном $n$-вершинном графе. Проведeн вероятностный анализ алгоритма для решения задачи со случайными входными данными (весами рeбер) в случае равномерного распределения весов рeбер и в случае распределений минорирующего типа. Показано, что предложенный алгоритм временно́й сложности $O(n^2+nd\ln n)$ находит асимптотически точное решение задачи при $d=o(n)$. В случае $d\leqslant n\ln n$ асимптотически точное решение может быть получено с временной сложностью $O(n^2)$. Для минимизационной версии задачи к условию асимптотической точности модифицированного алгоритма добавляется дополнительное ограничение на величину разброса значений весов рeбер графа.
Библ. 6.