Кандидатська дисертація. Градинар Іван Петрович. Алгоритми розв'язання деяких дискретних оптимізаційних задач великої розмірності на графах

Реєстраційний номер

0413U003067, Кандидатська дисертація

На здобуття

к.ф.-м.н.

Дата захисту

25-04-2013

Статус

Захищена

Назва роботи

Алгоритми розв'язання деяких дискретних оптимізаційних задач великої розмірності на графах

Здобувач

Градинар Іван Петрович,

Керівник Шило Володимир Петрович
Опонент Донець Георгій Панасович
Опонент Протасова Ксенія Дмитрівна

Установа, організація, у вченій раді якої відбудеться/відбувся захист

Інститут кібернетики ім. В.М. Глушкова

Опис

Дисертаційна робота присвячена питанням розробки та дослідження алгоритмів розв'язання дискретних оптимізаційних задач великої розмірності на графах. Побудовано математичну модель задачі знаходження максимальної ro-щільної множини вершин графу, доведено властивості такої множини, використані при розробці алгоритмів. Встановлено еквівалентність задачі упаковки множини максимальної ваги та задачі знаходження незалежної множини вершин графу максимальної ваги. Для пошуку наближених розв'язків дискретних оптимізаційних задач великої розмірності на графах розроблено підхід, заснований на використанні ідей методу глобального рівноважного пошуку. На його основі розроблено наближені алгоритми розв'язання наступних класів задач: знаходження максимальної незалежної множини (та незалежної множини максимальної ваги) вершин графу, упаковки множини максимальної ваги, пошуку максимального k-plex (co-k-plex) графу та k-plex (co-k-plex) максимальної ваги, максимальної ro-щільної множини вершин графу, максимального зваженого розрізу графу. На базі розроблених алгоритмів створено відповідне програмне забезпечення. Проведено експериментальні дослідження і порівняльний аналіз розроблених та відомих алгоритмів, які підтвердили ефективність побудованих алгоритмів. Запропоновано підходи до прискорення процесу розв'язання дискретних оптимізаційних задач великої розмірності на графах з використанням РЕСТАРТ-технології та методу Path-relinking.

Дата реєстрації

2013-05-14

Додано/оновлено в НРАТ

2020-04-04 / 2026-06-30