Об одном алгоритме нахождения минимального остова с ограниченным снизу диаметром

Рассматривается задача нахождения остовного дерева минимального веса с ограниченным снизу диаметром в полном $n$-вершинном взвешенном неориентированном графе. В общем случае эта задача NP-трудна. Предлагается алгоритм решения задачи с временной сложностью $O(n^2)$. В предположении, что веса ребер назначаются случайно, независимо и равновероятно из отрезка $(a^n,b^n)$ при $a^n>0$ (в непрерывном случае) или из множества $\{1,\dots,r_n\}$ (в дискретном случае), проводится вероятностный анализ предложенного алгоритма. Отдельно рассматриваются входы задачи, когда $b_n/a_n\leqslant n/\psi_n$ (соответственно при $r_n\leqslant n/\psi_n$) и нижняя оценка диаметра остовного дерева не превышает $d_n=n-n/\psi_n$ (где $\psi_n=o(n)$ и $\psi_n\to\infty$ при $n\to\infty$). В этом случае алгоритм с вероятностью, большей $1-\exp(-0,25n/\psi_n)$, имеет относительную погрешность, не превышающую величины $\ln\psi_n/\psi_n$ т. е. является асимптотически точным. Библиогр. 7.