Geodesic
Approximation algorithms for graph approximation problems
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 1, pp. 41-60

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

Some versions of the graph approximation problem are studied. Approximation algorithms for these problems are proposed and performance guarantees of the algorithms are obtained. In particular, it is shown that the problem of approximation by graphs with a bounded number of connected components belongs to the class APX. Ill. 1, bibliogr. 12.
Keywords: graph approximation problem, approximation algorithm, performance guarantee. 
@article{DA_2011_18_1_a4,
     author = {V. P. Il'ev and S. D. Il'eva and A. A. Navrotskaya},
     title = {Approximation algorithms for graph approximation problems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {41--60},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_1_a4/}
}
TY  - JOUR
AU  - V. P. Il'ev
AU  - S. D. Il'eva
AU  - A. A. Navrotskaya
TI  - Approximation algorithms for graph approximation problems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 41
EP  - 60
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_1_a4/
LA  - ru
ID  - DA_2011_18_1_a4
ER  - 
%0 Journal Article
%A V. P. Il'ev
%A S. D. Il'eva
%A A. A. Navrotskaya
%T Approximation algorithms for graph approximation problems
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 41-60
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_1_a4/
%G ru
%F DA_2011_18_1_a4
V. P. Il'ev; S. D. Il'eva; A. A. Navrotskaya. Approximation algorithms for graph approximation problems. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 1, pp. 41-60. http://geodesic.mathdoc.fr/item/DA_2011_18_1_a4/