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