А. А. Агеев, В. П. Ильев, А. В. Кононов, А. С. Талевнин, “Вычислительная сложность задачи аппроксимации графов”, Дискретн. анализ и исслед. опер., сер. 1, 2006, том 13, выпуск 1,страницы 3

Эта публикация цитируется в 30 статьях

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

А. А. Агеев^a, В. П. Ильев^b, А. В. Кононов^a, А. С. Талевнин^b

^a Институт математики им. С. Л. Соболева СО РАН
^b Омский государственный университет им. Ф. М. Достоевского

Аннотация: Исследуется вычислительная сложность известной задачи аппроксимации графов. Показано, что различные варианты этой задачи являются NP-трудными как для неориентированных, так и для ориентированных графов. Для одного варианта задачи доказано существование полиномиальной приближённой схемы.
Библ. 14.

УДК: 519.8

Статья поступила: 20.09.2005