We give a new approximation polynomial time algorithm for one of the intractable problem of finding given-diameter Minimum Spanning Tree (MST) on n-vertex complete graph with randomly weighted edges. A significant advantage of this algorithm is that it turned out to be well suited for finding several edge-disjoint MST of a given diameter. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an segment [a_n;b_n], a_n＞0. Sufficient conditions of asymptotic optimality are presented. It is also noteworthy that the new algorithmic approach to solve the problem of finding a given-diameter MST both on directed and undirected graphs.
展开▼
