This article is cited in 2 scientific papers (total in 2 papers)
Applied Graph Theory
Computational complexity of the problem of approximation by graphs with connected components of bounded size
V. P. Il'ev, A. A. Navrocka
Omsk State University, Omsk, Russia
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.
graph approximation, polynomial-time problem, $NP$-hard problem.
PDF file (562 kB)
V. P. Il'ev, A. A. Navrocka, “Computational complexity of the problem of approximation by graphs with connected components of bounded size”, Prikl. Diskr. Mat., 2011, no. 3(13), 80–84
Citation in format AMSBIB
\by V.~P.~Il'ev, A.~A.~Navrocka
\paper Computational complexity of the problem of approximation by graphs with connected components of bounded size
\jour Prikl. Diskr. Mat.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
V. P. Il'ev, S. D. Il'eva, A. A. Navrotskaya, “Graph clustering with a constraint on cluster sizes”, J. Appl. Industr. Math., 10:3 (2016), 341–348
A. V. Ilev, V. P. Ilev, “Ob odnoi zadache klasterizatsii grafa s chastichnym obucheniem”, PDM, 2018, no. 42, 66–75
|Number of views:|