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 ²
Shamardin Yury Vladislavovich ¹
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