|
Prikladnaya Diskretnaya Matematika, 2011, Number 3(13), Pages 80–84
(Mi pdm336)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 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
Abstract:
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.
Citation:
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
Linking options:
https://www.mathnet.ru/eng/pdm336 https://www.mathnet.ru/eng/pdm/y2011/i3/p80
|
Statistics & downloads: |
Abstract page: | 286 | Full-text PDF : | 92 | References: | 35 | First page: | 1 |
|