|
Дискретный анализ и исследование операций, сер. 1, 2006, том 13, выпуск 1, страницы 3–15
(Mi da20)
|
|
|
|
Эта публикация цитируется в 30 научных статьях (всего в 30 статьях)
Вычислительная сложность задачи аппроксимации графов
А. А. Агеевa, В. П. Ильевb, А. В. Кононовa, А. С. Талевнинb a Институт математики им. С. Л. Соболева СО РАН
b Омский государственный университет им. Ф. М. Достоевского
Аннотация:
Исследуется вычислительная сложность известной задачи аппроксимации графов. Показано, что различные варианты этой задачи являются NP-трудными как для неориентированных, так и для ориентированных графов. Для одного варианта задачи доказано существование полиномиальной приближённой схемы.
Библ. 14.
Статья поступила: 20.09.2005
Образец цитирования:
А. А. Агеев, В. П. Ильев, А. В. Кононов, А. С. Талевнин, “Вычислительная сложность задачи аппроксимации графов”, Дискретн. анализ и исслед. опер., сер. 1, 13:1 (2006), 3–15; J. Appl. Industr. Math., 1:1 (2007), 1–8
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da20 https://www.mathnet.ru/rus/da/v13/s1/i1/p3
|
Статистика просмотров: |
Страница аннотации: | 462 | PDF полного текста: | 273 | Список литературы: | 62 |
|