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/

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

[2] Veiner G. A., “Ob approksimatsii simmetrichnogo refleksivnogo binarnogo otnosheniya otnosheniem ekvivalentnosti”, Tr. Tallinsk. politekhn. in-ta. Ser. A, 313, 1971, 45–49

[3] Gimadi E. Kh., Glebov N. I., Perepelitsa V. A., “Algoritmy s otsenkami dlya zadach diskretnoi optimizatsii”, Problemy kibernetiki, 31, Nauka, M., 1975, 35–42

[4] Ilev V. P., Ileva S. D., “Priblizhënnye algoritmy approksimatsii grafami s ogranichennym chislom komponent”, Tr. In-ta matematiki NAN Belarusi, 18:1 (2010), 47–52

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

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

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

[8] Fridman G. Sh., “Odna zadacha approksimatsii grafov”, Upravlyaemye sistemy, 8, 1971, 73–75

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

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

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

[12] Zahn C., “Approximating symmetric relations by equivalence relations”, J. SIAM, 12:4 (1964), 840–847 | MR | Zbl