Реферат: We consider the following NP-hard generalization of the Minimum Spanning Tree problem. Given an undirected n-vertex edge-weighted complete graph and integers d and m, find m edge-disjoint spanning trees of diameter at most d and minimum total weight. We propose a new polynomial-time approximation algorithm for the problem and study its performance guarantees on random inputs, that is, when the edge-weights of the graph are i.i.d random variables. We show that under mild conditions on the distribution parameters the proposed algorithm is asymptotically optimal in the case of continuous and discrete uniform distribution on [a_n, b_n], a_n>0, shifted exponential distribution with shift a_n>0, and distributions dominating the above. In contrast to a number of previous results for related problems, the new algorithm is asymptotically optimal not only if d tends to infinity with n, but for constant d as well.

Библиографическая ссылка: Gimadi E.K. , Tsidulko O.Y.
Edge-disjoint spanning trees of arbitrary bounded diameter on random inputs
Ural mathematical journal. 2025. V.11. N2. P.100–118. DOI: 10.15826/umj.2025.2.007 Scopus РИНЦ

Даты:

Поступила в редакцию:	27 мая 2025 г.
Принята к публикации:	24 нояб. 2025 г.
Опубликована в печати:	13 янв. 2026 г.
Опубликована online:	13 янв. 2026 г.

Идентификаторы БД:

Scopus:	2-s2.0-105027125222
РИНЦ:	88758111

Цитирование в БД: Пока нет цитирований

Альметрики: