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

Рассматриваются графы с классом матриц, элементы которых – веса рёбер – выбираются случайно и независимо из неограниченного сверху интервала с непрерывной функцией распределения. Проведён вероятностный анализ приближённого алгоритма с квадратичной временно́й сложностью в случае экспоненциального распределения. Обоснованы достаточные условия асимптотической точности алгоритма. Аналогичные условия получены также в случае усечённо-нормального распределения. Ил. 2, библиогр. 17.