Архів номерів > Том 36, № 1 (2014)

Метод перечисления максимальных независимых множеств в произвольных неориентированных графах

С.В. Листровой, д-р техн. наук
Украинская государственная академия железнодорожного транспорта

Анотація

Запропоновано процедуру перелічування тільки максимальних незалежних множин у неорієнтованих довільних графах, яка дозволяє зменшити часову складність реалізації алгоритму.

Ключові слова:

максимальные независимые множества, клики.

Список літератури

1. Кристофидес Н. Теория графов. Алгоритмический подход.—М. : Мир, 1978.— 309 с.
2. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. — М. : Наука, 1990.— 383 c.
3. Листровой С.В., Яблочков С.В. Метод решения задачи определения минимальных вершинных покрытий и независимых максимальных множеств // Электрон. моделирование. — 2003.— 25, № 2. — С. 31—40.
4. Листровой С.В., Гуль А.Ю. Метод решения задачи о минимальном покрытии на основе рангового подхода // Там же. — 1999. — 21,№1—С. 58—70.

Повний текст: PDF