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