Статьи автора

Об асимптотической точности поиска минимума суммы весов разнореберных остовных деревьев фиксированного диаметра

Номер выпуска 7 от 15.07.2023

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

1 0