| Title: | Исследование задачи о наибольшем 2-диссоциирующем множестве |
| Authors: | Бердник, Л. А. |
| Keywords: | материалы конференций;эвристические алгоритмы;графы;линейные модели |
| Issue Date: | 2025 |
| Publisher: | БГУИР |
| Citation: | Бердник, Л. А. Исследование задачи о наибольшем 2-диссоциирующем множестве / Я. Д. Бекетаў // Компьютерные системы и сети : материалы 61-й научной конференции аспирантов, магистрантов и студентов, Минск, 22–26 апреля 2025 г. / Белорусский государственный университет информатики и радиоэлектроники. – Минск, 2025. – С. 471–472. |
| Abstract: | Исследование рассматривает задачу нахождения наибольшего 2-диссоциирующего множества в неориентированном графе –
подмножества вершин, порождающее подграф с максимальной степенью вершин не больше, чем 2. В работе изучаются
структурные и алгоритмические аспекты задачи, формулируется ее содержательная, распознавательная и оптимизационная
постановки, а также предлагается целочисленная линейная модель задачи. Особое внимание уделяется разработке и
сравнительному анализу четырех эвристических алгоритмов: жадного, случайного, локального поиска и метода имитации отжига,
которые тестируются на случайных графах Эрдеша–Реньи. |
| URI: | https://libeldoc.bsuir.by/handle/123456789/60351 |
| Appears in Collections: | Компьютерные системы и сети : материалы 61-й научной конференции аспирантов, магистрантов и студентов : сборник статей (2025)
|
