Том 6, серия 1, номер 4, 1999 г., Стр. 3-19

УДК 519.17
В. Е. Алексеев
Полиномиальный алгоритм для нахождения наибольших независимых множеств в графах без вилок

Аннотация:
Вилка – это граф, получаемый из звезды $K_{1,3}$ подразбиением одного ребра. Известно [6-8], что для графов без звезд задача нахождения наибольшего независимого множества решается за полиномиальное время. Доказывается, что это верно и для более широкого класса графов без вилок.
Библиогр. 9.

Алексеев В. Е. ¹
1. Нижегородский государственный университет,
пр. Гагарина, 23, корп. 2, 603600 Нижний Новгород, ГСП-20, Россия
е-mail: aleve@mail.ru

Статья поступила 14 января 1999 г.
Исправленный вариант — 19 июля 1999 г.