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/

[1] Astrakov S. N., Erzin A. I., Zalyubovskii V. V., “Sensornye seti i pokrytie ploskosti krugami”, Diskret. analiz i issled. operatsii, 16:3 (2009), 3–19 | MR | Zbl

[2] Tot L. F., Raspolozheniya na ploskosti, na sfere i v prostranstve, Fizmatgiz, M., 1958, 365 pp.

[3] Althaus E., et al., “Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks”, Wireless Networks, 12:3 (2006), 287–299 | DOI

[4] Berman P., Karpinski M., “On some tighter inapproximability results”, Electron. Colloquium Computational Complexity (ECCC), 1998, TR98–065

[5] Clementi A. E. F., Penna P., Silvestri R., “On the power assignment problem in radio networks”, Electron. Colloquium Computational Complexity (ECCC), 2000, TR00–054

[6] Carmi P., Katz M. L., “Power assignment in radio networks with two power levels”, Algorithmica, 47 (2007), 183–201 | DOI | MR | Zbl

[7] Diane M., Plesnik J., “An integer programming formulation of the Steiner problem in graphs”, Math. Methods Oper. Res., 37 (1993), 107–111 | DOI | MR | Zbl

[8] Kershner R., “The number of circles covering a set”, Amer. J. Math., 61:3 (1939), 665–671 | DOI | MR | Zbl

[9] Kirousis L. M., Kranakis E., Krizanc D., Pelc A., “Power consumption in packet radio networks”, Theor. Comput. Sci., 243 (2000), 289–305 | DOI | MR | Zbl

[10] Pottie G. J., Kaiser W. J., “Wireless integrated network sensors”, Commun. ACM, 43:5 (2000), 51–58 | DOI

[11] Tóth F. G., “Covering the plane with two kinds of circles”, Discrete Comput. Geometry, 13:3 (1995), 445–457 | DOI | MR | Zbl

[12] Wu J., Dai F., “Virtual backbone construction in MANETs using adjustable transmission ranges”, IEEE Trans. Mobile Comput., 5:9 (2006), 1188–1200 | DOI

[13] Wu J., Yang S., “Energy-efficient node scheduling models in sensor networks with adjustable ranges”, Int. J. Found. Comput. Sci., 16:1 (2005), 3–17 | DOI | MR | Zbl

[14] Zhang H., Hou J. C., “Maintaining sensing coverage and connectivity in large sensor networks”, Ad Hoc Sensor Wireless Networks, 1:1–2 (2005), 89–124