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

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

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

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

Ильев Виктор Петрович ¹
Ильева Светлана Диадоровна ²
Навроцкая Анна Александровна ¹
1. Омский гос. университет,
пр. Мира, 55а, 644077 Омск, Россия
2. ООО «Омсктелеком»,
ул. 1-я Заводская, 23, 644040 Омск, Россия
е-mail: iljev@mail.ru, iljeva@mail.ru, nawrocki@yandex.ru

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

Литература

[1] Агеев А. А., Ильев В. П., Кононов А. В., Талевнин А. С. Вычислительная сложность задачи аппроксимации графов // Дискрет. анализ и исслед. операций. Сер. 1. — 2006. — Т. 13, № 1. — C. 3–15.

[2] Вейнер Г. А. Об аппроксимации симметричного рефлексивного бинарного отношения отношением эквивалентности // Тр. Таллинск. политехн. ин-та. Сер. А. — 1971. — № 313. — С. 45–49.

[3] Гимади Э. Х., Глебов Н. И., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. — М.: Наука, 1975. — Вып. 31. — С. 35–42.

[4] Ильев В. П., Ильева С. Д. Приближённые алгоритмы аппроксимации графами с ограниченным числом компонент // Тр. Ин-та математики НАН Беларуси. — 2010. — Т. 18, № 1. — C. 47–52.

[5] Ильев В. П., Фридман Г.Ш. К задаче аппроксимации графами с фиксированным числом компонент // Докл. АН СССР. — 1982. — Т. 264, № 3. — С. 533–538.

[6] Ляпунов А. А. О строении и эволюции управляющих систем в связи с теорией классификации // Проблемы кибернетики. — М.: Наука, 1973. — Вып. 27. — С. 7–18.

[7] Талевнин А. С. О сложности задачи аппроксимации графов // Вестн. Омск. ун-та. — 2004. — № 4. — C. 22–24.

[8] Фридман Г. Ш. Одна задача аппроксимации графов // Управляемые системы. — 1971. — Вып. 8. — С. 73–75.

[9] Фридман Г. Ш. О некоторых результатах в задаче аппроксимации графов // Проблемы анализа дискретной информации. Ч. I. — Новосибирск: ИЭиООП СО АН СССР, 1975. — С. 125–152.

[10] Фридман Г. Ш. Исследование одной задачи классификации на графах // Методы моделирования и обработки информации. — Новосибирск: Наука, 1976. — С. 147–177.

[11] Tomescu I. La reduction minimale d’un graphe à une reunion des cliques // Discrete Math. — 1974. — V. 10, N 1–2. — P. 173–179.

[12] Zahn C. Approximating symmetric relations by equivalence relations // J. SIAM. — 1964. — V. 12, N 4. — P. 840–847.