Search academic texts

Information × Registration Number 0413U003067, Candidate dissertation Status к.ф.-м.н. Date 25-04-2013 popup.evolution o 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 Протасова Ксенія Дмитрівна Description Дисертаційна робота присвячена питанням розробки та дослідження алгоритмів розв'язання дискретних оптимізаційних задач великої розмірності на графах. Побудовано математичну модель задачі знаходження максимальної ro-щільної множини вершин графу, доведено властивості такої множини, використані при розробці алгоритмів. Встановлено еквівалентність задачі упаковки множини максимальної ваги та задачі знаходження незалежної множини вершин графу максимальної ваги. Для пошуку наближених розв'язків дискретних оптимізаційних задач великої розмірності на графах розроблено підхід, заснований на використанні ідей методу глобального рівноважного пошуку. На його основі розроблено наближені алгоритми розв'язання наступних класів задач: знаходження максимальної незалежної множини (та незалежної множини максимальної ваги) вершин графу, упаковки множини максимальної ваги, пошуку максимального k-plex (co-k-plex) графу та k-plex (co-k-plex) максимальної ваги, максимальної ro-щільної множини вершин графу, максимального зваженого розрізу графу. На базі розроблених алгоритмів створено відповідне програмне забезпечення. Проведено експериментальні дослідження і порівняльний аналіз розроблених та відомих алгоритмів, які підтвердили ефективність побудованих алгоритмів. Запропоновано підходи до прискорення процесу розв'язання дискретних оптимізаційних задач великої розмірності на графах з використанням РЕСТАРТ-технології та методу Path-relinking. Registration Date 2013-04-25 popup.nrat_date 2020-04-04 Close