Том 10, серия 1, номер 3, 2003 г., Стр. 54-66

УДК 519.8
В. П. Ильев, А. С. Талевнин
Две задачи на наследственных системах

Аннотация:
Исследуются задачи о максимальном независимом и минимальном зависимом множестве наследственной системы, которые могут быть рассмотрены как задачи о максимальном независимом множестве вершин и минимальном вершинном покрытии в гиперграфе соответственно. Для приближенного решения невзвешенной задачи о независимом множестве предложен алгоритм градиентного типа. В предположении, что гиперграф не содержит ребер мощности 1, доказано, что этот алгоритм всегда дает решение, которое не более чем в $(\bar d+2)/2$ раз хуже оптимального, где $\bar d$ – средняя степень вершин гиперграфа. Показана эквивалентность задачи о минимальном зависимом множестве задаче о покрытии множества, что позволяет применить для ее решения известный алгоритм Хватала. Этот алгоритм находит решение, отличающееся от оптимального не более чем в $1+\ln\Delta$ раз, где $\Delta$ – максимальная степень вершин гиперграфа.

Ильев В. П. ¹
Талевнин А. С. ¹
1. Омский государственный университет
пр. Мира 55А, 644077 Омск, Россия
е-mail: iljev@iitam.omsk.net.ru, talants@rambler.ru

Статья поступила 15 мая 2003 г.
Исправленный вариант — 6 июня 2003 г.