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

Registration Number

0413U003067, Candidate dissertation

Status

к.ф.-м.н.

Date

25-04-2013

popup.evolution

.

Title

Algorithms for solving some high-dimensional discrete optimization problems on graphs

Author

Gradinar Ivan Petrovych,

popup.head Shylo Volodymyr Petrovych
popup.opponent Донець Георгій Панасович
popup.opponent Протасова Ксенія Дмитрівна

popup.rada

V.M.Glushkov Institute of Cybernetics of NASU

Description

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

Registration Date

2013-05-14

popup.nrat_date

2020-04-04 / 2026-06-30