В. П. Ильев, С. Д. Ильева, А. А. Навроцкая, “Приближённые алгоритмы для задач аппроксимации графов”, Дискретн. анализ и исслед. опер., 2011, том 18, выпуск 1,страницы 41

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

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

В. П. Ильев^a, С. Д. Ильева^b, А. А. Навроцкая^a

^a Омский гос. университет, Омск, Россия
^b ООО "Омсктелеком", Омск, Россия

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

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

УДК: 519.8

Статья поступила: 20.07.2010
Переработанный вариант: 29.11.2010