Geodesic
Computational complexity of the problem of approximation by graphs with connected components of bounded size
Prikladnaâ diskretnaâ matematika, no. 3 (2011), pp. 80-84.

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

New versions of the graph approximation problem with the bounded size of connected components in approximating graphs are proposed. It is shown that if the cardinality of each component in the approximating graphs is less or equal to the given integer $p \geqslant 3$ then the graph approximation problem is $NP$-hard, whereas in the case of $p=2$ the problem is solvable in a polynomial time.
Keywords: graph approximation, polynomial-time problem, $NP$-hard problem. 
@article{PDM_2011_3_a5,
     author = {V. P. Il'ev and A. A. Navrocka},
     title = {Computational complexity of the problem of approximation by graphs with connected components of bounded size},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {80--84},
     publisher = {mathdoc},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2011_3_a5/}
}
TY  - JOUR
AU  - V. P. Il'ev
AU  - A. A. Navrocka
TI  - Computational complexity of the problem of approximation by graphs with connected components of bounded size
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2011
SP  - 80
EP  - 84
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2011_3_a5/
LA  - ru
ID  - PDM_2011_3_a5
ER  - 
%0 Journal Article
%A V. P. Il'ev
%A A. A. Navrocka
%T Computational complexity of the problem of approximation by graphs with connected components of bounded size
%J Prikladnaâ diskretnaâ matematika
%D 2011
%P 80-84
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2011_3_a5/
%G ru
%F PDM_2011_3_a5
V. P. Il'ev; A. A. Navrocka. Computational complexity of the problem of approximation by graphs with connected components of bounded size. Prikladnaâ diskretnaâ matematika, no. 3 (2011), pp. 80-84. http://geodesic.mathdoc.fr/item/PDM_2011_3_a5/

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

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

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

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

[5] Zahn C., “Approximating symmetric relations by equivalence relations”, J. Soc. Indust. Appl. Math., 12:4 (1964), 840–847 | DOI | MR | Zbl

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

[7] Edmonds J., “Paths, trees, and flowers”, Canad. J. Math., 17:3 (1965), 449–467 | DOI | MR | Zbl

[8] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR