Abstract: 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.

Cite: 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 РИНЦ

Dates:

Submitted:	May 27, 2025
Accepted:	Nov 24, 2025
Published print:	Jan 13, 2026
Published online:	Jan 13, 2026

Identifiers:

Scopus:	2-s2.0-105027125222
Elibrary:	88758111

Citing: Пока нет цитирований

Altmetrics: