Volume 20, No 1, 2013, P. 1227
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 minweight spanning tree with edges' weights in $[a,b]$ is a $\bigl(2\frac{2a}{a+b+2b/(n2)}\bigr)$approximation solution and the problem of constructing a 1,00048 approximation solution is NPhard. 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
email: adilerzin@math.nsc.ru, nomad87@ngs.ru, orlab@math.nsc.ru
