The Problem of Finding Several Given Diameter Spanning Trees of Maximum Total Weight in a Complete Graph

We consider the following NP-hard problem. Given an undirected complete edge-weighted graph and positive integers m, D, the goal is to find m edge-disjoint spanning trees with diameter D of maximum total weight in complete undirected graph. We propose an $$\mathcal O(n^2)$$ -time approximation algorithm for the problem, where n is the number of vertices in the input graph. For the case when edge weights are randomly uniformly chosen from the interval (0; 1), we prove sufficient conditions under which the proposed algorithm gives asymptotically optimal solutions.