Modeling and Optimizing for NP-hard Problems in Graph Theory
This PhD thesis introduces optimization methods for graph problems classified as NP-hard. These are problems for which no deterministic algorithm is capable of solving them in polynomial time. More specifically, three graph problems were addressed, and for each, different optimization methods were u...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Dissertation |
| Published: |
2024-05-10
|
| Subjects: | |
| doi: | 10.14232/phd.12021 |
| mtmt: | 35673840 |
| Online Access: | http://doktori.ek.szte.hu/12021 |
| Summary: | This PhD thesis introduces optimization methods for graph problems classified as NP-hard. These are problems for which no deterministic algorithm is capable of solving them in polynomial time. More specifically, three graph problems were addressed, and for each, different optimization methods were used. These methods include standard methods, metaheuristics, and heuristics. In all cases, the performance of these methods was compared with those proposed in the literature, considering factors such as execution time and the quality of the solutions achieved. This comparative analysis aims to demonstrate the effectiveness of the proposed optimization methods. Ez a PhD értkezés optimalizációs módszereket mutat be NP-nehéz gráfproblémákhoz. Ezen feladatok megoldására, jelen tudásunk szerint, nem léteznek polinomiális időben végrehajtható algoritmusok. Konkrétan három gráfproblémát vizsgáltunk, és mindegyikhez különböző optimalizációs módszereket alkalmaztunk, úgy mint egészértékű lineáris programozás, metaheurisztikák és heurisztikák. Minden esetben a javasolt módszerek teljesítményét összehasonlítottuk a szakirodalomban találhatóakkal, figyelembe véve olyan tényezőket, mint a végrehajtási idő és az elért megoldások minősége. Az összehasonlító elemzéseink célja a javasolt optimalizációs módszerek hatékonyságának bemutatása. |
|---|---|
| Physical Description: | 95 |