Geodesic
Approximation algorithms for approximating graphs with bounded numberof connected components
Trudy Instituta matematiki, Tome 18 (2010) no. 1, pp. 47-52

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

The following graph approximation problem is studied: given an undirected graph, one has to find the nearest graph on the same vertex set all connected components of which are the complete graphs. The distance between graphs is equal to the number of noncoinciding edges. The brief survey of the known results is given. The constant-factor approximation algorithms for two versions of the graph approximation problem are proposed. 
@article{TIMB_2010_18_1_a5,
     author = {V. P. Il'ev and S. D. Il'eva},
     title = {Approximation algorithms for approximating graphs with bounded numberof connected components},
     journal = {Trudy Instituta matematiki},
     pages = {47--52},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2010_18_1_a5/}
}
TY  - JOUR
AU  - V. P. Il'ev
AU  - S. D. Il'eva
TI  - Approximation algorithms for approximating graphs with bounded numberof connected components
JO  - Trudy Instituta matematiki
PY  - 2010
SP  - 47
EP  - 52
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMB_2010_18_1_a5/
LA  - ru
ID  - TIMB_2010_18_1_a5
ER  - 
%0 Journal Article
%A V. P. Il'ev
%A S. D. Il'eva
%T Approximation algorithms for approximating graphs with bounded numberof connected components
%J Trudy Instituta matematiki
%D 2010
%P 47-52
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMB_2010_18_1_a5/
%G ru
%F TIMB_2010_18_1_a5
V. P. Il'ev; S. D. Il'eva. Approximation algorithms for approximating graphs with bounded numberof connected components. Trudy Instituta matematiki, Tome 18 (2010) no. 1, pp. 47-52. http://geodesic.mathdoc.fr/item/TIMB_2010_18_1_a5/