By this author

On Asymptotically Optimal Approach for Finding of the Minimum Total Weight of Edge-Disjoint Spanning Trees with a Given Diameter

Issue number 7 from 15.07.2023

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

4 0