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

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