Geodesic
Approximation algorithms for approximating graphs with bounded numberof connected components
Trudy Instituta matematiki, Tome 18 (2010) no. 1, pp. 47-52 
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/
@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},
     year = {2010},
     volume = {18},
     number = {1},
     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
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
%U http://geodesic.mathdoc.fr/item/TIMB_2010_18_1_a5/
%G ru
%F TIMB_2010_18_1_a5

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.

[1] Zahn C., “Approximating symmetric relations by equivalence relations”, J. of the Society for Industrial and Applied Mathematics, 12:4 (1964), 840–847 | DOI | MR | Zbl

[2] Lyapunov A.A., “O stroenii i evolyutsii upravlyayuschikh sistem v svyazi s teoriei klassifikatsii”, Problemy kibernetiki, 27, Nauka, M., 1973, 7–18

[3] Mirkin B.G., “Zadachi approksimatsii v prostranstve otnoshenii i analiz nechislovykh dannykh”, Avtomatika i telemekhanika, 1974, no. 9, 53–61

[4] Tyshkevich R.I., “Matroidnye razlozheniya grafa”, Diskretnaya matematika, 1:3 (1989), 129–138 | MR | Zbl

[5] Fridman G.Sh., “Odna zadacha approksimatsii grafov”, Upravlyaemye sistemy. Sb. nauch. tr., 8, Institut matematiki SO AN SSSR, Novosibirsk, 1971, 73–75

[6] Edmonds J., “Paths, trees, and flowers”, Canadian J. of Mathematics, 17:3 (1965), 449–467 | DOI | MR | Zbl

[7] Fridman G.Sh., “Ob odnom neravenstve v zadache approksimatsii grafov”, Kibernetika, 1974, no. 3, 151

[8] Fridman G.Sh., “Issledovanie odnoi zadachi klassifikatsii na grafakh”, Metody modelirovaniya i obrabotki informatsii, Nauka, Novosibirsk, 1976, 147–177

[9] Tomescu I., “La reduction minimale d'un graphe à une reunion de cliques”, Discrete Math., 10:1-2 (1974), 173–179 | DOI | MR | Zbl

[10] Ilev V.P., Fridman G.Sh., “K zadache approksimatsii grafami s fiksirovannym chislom komponent”, Dokl. AN SSSR, 264:3 (1982), 533–538 | MR

[11] Fridman G.Sh., “Polinomialnaya polnota nekotorykh modifikatsii zadachi approksimatsii grafov”, Tez. dokl. IV Vsesoyuz. konf. po problemam teoreticheskoi kibernetiki, Novosibirsk, 1977, 150

[12] Talevnin A.S., “O slozhnosti zadachi approksimatsii grafov”, Vestn. Omskogo un-ta, 2004, no. 4, 22–24

[13] Ageev A.A., Ilev V.P., Kononov A.V., Talevnin A.S., “Vychislitelnaya slozhnost zadachi approksimatsii grafov”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 13:1 (2006), 3–15 | MR

[14] Veiner G.A., “Ob approksimatsii simmetrichnogo refleksivnogo binarnogo otnosheniya otnosheniem ekvivalentnosti”, Tr. Tallinskogo politekh. in-ta. Ser. A, 313 (1971), 45–49

[15] Fridman G.Sh., “O nekotorykh rezultatakh v zadache approksimatsii grafov”, Problemy analiza diskretnoi informatsii, IEiOOP SO AN SSSR, Novosibirsk, 1975, 125–152