Эвристический алгоритм для поиска наибольшего независимого множества

• Опубліковано в: : Кибернетика и системный анализ
• Дата: 2012
• Автор: Плотников, А.Д.
• Формат: Стаття
• Мова: Russian
• Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2012
• Теми: Кибернетика
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/84142
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Эвристический алгоритм для поиска наибольшего независимого множества / А.Д. Плотников // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 41-48. — Бібліогр.: 6 назв. — рос.

Розроблено евристичний алгоритм для розв’язання задачі пошуку найбільшої незалежної множини вершин в неорієнтованому графі. Для цього використано підхід скінченних частково впорядкованих множин, зокрема техніка розбиття такої множини на мінімальне число ланцюгів. Побудовано спеціальний орграф, i на ocнові гіпотези про його властивості запропоновано розв’язувальний алгоритм. Наведено дані експериментів на відомих прикладах. A heuristic algorithm is developed for finding the maximum independent set of vertices in an undirected graph. To this end, the technique of finite partially ordered sets is used, in particular, the technique of partitioning such a set into the minimum number of chains. A special digraph is constructed and a solution algorithm is proposed on the basis of the hypothesis about its properties. Some experimental data are presented for well-known examples