HomeIssuesComputational complexity of the problem of approximation by graphs with connected components of bounded size

Computational complexity of the problem of approximation by graphs with connected components of bounded size | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 3(13).

New versions of the graph approximation problemwith 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 lessor equal to the given integer p ^ 3 then the graph approximation problem is NP-hard,whereas in the case of P = 2 the problem is solvable in a polynomial time.
Download file
Counter downloads: 64
  • Title Computational complexity of the problem of approximation by graphs with connected components of bounded size
  • Headline Computational complexity of the problem of approximation by graphs with connected components of bounded size
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(13)
  • Date:
  • DOI
Keywords
NP-hard problem, polynomial-time problem, graph approximation, NP-трудная задача, полиномиально разрешимая задача, аппроксимация графа
Authors
References
Edmonds J. Paths, trees, and flowers // Canad. J. Math. 1965. V. 17. No. 3. P. 449-467.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
Zahn C. Approximating symmetric relations by equivalence relations // J. Soc. Indust. Appl. Math. 1964. V. 12. No. 4. P. 840-847.
Агеев А. А., Ильев В. П., Кононов А. В., Талевнин А. С. Вычислительная сложность задачи аппроксимации графов // Дискрет. анализ и исслед. опер. Сер. 1. 2006. Т. 13. №1. С. 3-15.
Tomescu I. La reduction minimale d'un graphe a une reunion de cliques // Discrete Math. 1974. V. 10. No. 1-2. P. 173-179.
Фридман Г. Ш. Исследование одной задачи классификации на графах // Методы моделирования и обработки информации. Новосибирск: Наука, 1976. С. 147-177.
Ляпунов А. А. О строении и эволюции управляющих систем в связи с теорией классификации // Проблемы кибернетики. Вып. 27. М.: Наука, 1973. С. 7-18.
Ильев В. П., Фридман Г. Ш. К задаче аппроксимации графами с фиксированным числом компонент // Докл. АН СССР. 1982. Т. 264. №3. С. 533-538.
Computational complexity of the problem of approximation by graphs with connected components of bounded size | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 3(13).
Computational complexity of the problem of approximation by graphs with connected components of bounded size | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 3(13).
Download full-text version
Counter downloads: 249
Download file