EN|RU Volume 20, No 1, 2013, P. 12-27 UDC 519.8 Erzin A. I., Plotnikov R. V., Shamardin Yu. V.  Some polynomially solvable cases and approximation algorithms for optimal communication tree construction problem Abstract: 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. Keywords: communication network, spanning tree, approximation algorithm. Erzin Adil Il’yasovich 1,2 Plotnikov Roman Viktorovich 2 Shamardin Yury Vladislavovich 1 1. S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia 2. Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia e-mail: adilerzin@math.nsc.ru, nomad87@ngs.ru, orlab@math.nsc.ru © Sobolev Institute of Mathematics, 2015