Some polynomially solvable cases and approximation algorithms for optimal communication tree construction problem

In an arbitrary undirected $n$-node graph with nonnegative edges' weights, it is necessary to construct a spanning tree with minimal node sum of maximal weights of incident edges. Special cases when the problem is polynomially solvable are found. It is shown that a min-weight spanning tree with edges' weights in $[a,b]$ is a $\bigl(2-\frac{2a}{a+b+2b/(n-2)}\bigr)$-approximation solution and the problem of constructing a 1,00048- approximation solution is NP-hard. A heuristic polynomial algorithm is proposed and its a posteriori analysis is carried out. Tab. 4, ill. 4, bibliogr. 14.