Том 13, серия 1, номер 1, 2006 г., Стр. 3-15

УДК 519.8
А. А. Агеев, В. П. Ильев, А. В. Кононов, А. С. Талевнин
Вычислительная сложность задачи аппроксимации графов

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

Агеев А. А. ¹
Ильев В. П. ²
Кононов А. В. ¹
Талевнин А. С. ²
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Омский государственный университет,
пр. Мира, 55а, 644077 Омск, Россия
е-mail: ageev@math.nsc.ru, iljev@iitam.omsk.net.ru, alvenko@math.nsc.ru

Статья поступила 20 сентября 2005 г.