Geodesic
Some polynomially solvable cases and approximation algorithms for optimal communication tree construction problem
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 1, pp. 12-27

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2013_20_1_a1,
     author = {A. I. Erzin and R. V. Plotnikov and Yu. V. Shamardin},
     title = {Some polynomially solvable cases and approximation algorithms for optimal communication tree construction problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {12--27},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_1_a1/}
}
TY  - JOUR
AU  - A. I. Erzin
AU  - R. V. Plotnikov
AU  - Yu. V. Shamardin
TI  - Some polynomially solvable cases and approximation algorithms for optimal communication tree construction problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 12
EP  - 27
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_1_a1/
LA  - ru
ID  - DA_2013_20_1_a1
ER  - 
%0 Journal Article
%A A. I. Erzin
%A R. V. Plotnikov
%A Yu. V. Shamardin
%T Some polynomially solvable cases and approximation algorithms for optimal communication tree construction problem
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 12-27
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_1_a1/
%G ru
%F DA_2013_20_1_a1
A. I. Erzin; R. V. Plotnikov; Yu. V. Shamardin. Some polynomially solvable cases and approximation algorithms for optimal communication tree construction problem. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 1, pp. 12-27. http://geodesic.mathdoc.fr/item/DA_2013_20_1_a1/