An Asymptotically Optimal Algorithm for the Minimum Weight Spanning Tree with Arbitrarily Bounded Diameter on Random Inputs
摘要
We consider the problem of finding minimum-weight spanning tree with a diameter, which is either at most or equal to a given bound d, in a complete edge-weighted undirected graph. We propose a new simple polynomial-time approximation algorithm for this problem and provide probabilistic analysis of the algorithm on random inputs in which the weights of edges are i.i.d. random variables with either uniform continuous distribution on $$[a_n,b_n]$$ or uniform discrete distribution on segment $$[a_n,b_n] \cap \mathbb N$$ , $$0