ГлавнаяАрхивВычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера

Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера | Прикладная дискретная математика. 2011. № 3(13).

Рассматриваются новые варианты задачи аппроксимации графа, в которых имеются ограничения на размер компонент связности аппроксимирующих графов. Доказано, что если в качестве последних допускаются графы с компонентами связности мощностей 1, 2, . . . , p ^ 3, то задача аппроксимации графа является NP-трудной, а в случае p = 2 она полиномиально разрешима.
  • Title Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера
  • Headline Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3(13)
  • Date:
  • DOI
Ключевые слова
NP-hard problem, polynomial-time problem, graph approximation, NP-трудная задача, полиномиально разрешимая задача, аппроксимация графа
Авторы
Ссылки
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.
Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера | Прикладная дискретная математика. 2011. № 3(13).
Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера | Прикладная дискретная математика. 2011. № 3(13).
Полнотекстовая версия