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

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An Asymptotically Optimal Algorithm for the Minimum Weight Spanning Tree with Arbitrarily Bounded Diameter on Random Inputs

  • Edward Kh. Gimadi,
  • Oxana Yu. Tsidulko

摘要

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