EN|RU

Том 18, номер 1, 2011 г., Стр. 41-60

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

Аннотация:
Рассматриваются несколько вариантов задачи аппроксимации графа. Предложены приближённые алгоритмы для этих задач, получены гарантированные оценки точности алгоритмов. В частности, показано, что задача аппроксимации графами с ограниченным числом компонент связности принадлежит классу APX.
Ил. 1, библиогр. 12.

Ключевые слова: задача аппроксимации графа, приближённый алгоритм, гарантированная оценка точности.

Ильев Виктор Петрович 1
Ильева Светлана Диадоровна 2
Навроцкая Анна Александровна 1

1. Омский гос. университет,
пр. Мира, 55а, 644077 Омск, Россия
2. ООО «Омсктелеком»,
ул. 1-я Заводская, 23, 644040 Омск, Россия
е-mail: iljev@mail.ru, iljeva@mail.ru, nawrocki@yandex.ru

Статья поступила 20 июля 2010 г.
Исправленный вариант — 29 ноября 2010 г.

 © Институт математики им. С. Л. Соболева, 2015