Abstract:
We consider the intractable problem of finding several edge-disjoint spanning trees of the minimum total weight with a given diameter in complete undirected graph in current paper. The weights of edges of a graph are random variables from several continuous distributions: uniform, biased truncated exponential, biased truncated normal. The approximation algorithm with time complexity $\mathcal{O}(n^2)$, where n is number of vertices in graph, is proposed for solving this problem. The asymptotic optimality conditions for constructed algorithm is presented for each considered probabilistic distribution.