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...

Full description

Saved in:
Bibliographic Details
Main Author: Anaqreh Ahmad
Other Authors: Gazdag-Tóth Boglárka
Vinkó Tamás
Format: Dissertation
Published: 2024-05-10
Subjects:
Online Access:http://doktori.ek.szte.hu/12021
LEADER 02342nta a2200241 i 4500
001 dokt12021
005 20240523135535.0
008 240109s2024 hu om 000 eng d
040 |a SZTE Doktori Repozitórium  |b hun 
041 |a eng 
100 1 |a Anaqreh Ahmad 
245 1 0 |a Modeling and Optimizing for NP-hard Problems in Graph Theory  |h [elektronikus dokumentum] /  |c  Anaqreh Ahmad 
246 1 0 |a Modellezés és optimalizálás NP-nehez problémákhoz gráfelméletben  |h [elektronikus dokumentum] 
260 |c 2024-05-10 
502 |a Disszertacio 
520 3 |a 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. 
520 3 |a 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. 
650 4 |a informatikai tudományok 
650 4 |a Számítás- és információtudomány 
700 0 2 |a Gazdag-Tóth Boglárka  |e ths 
700 0 2 |a Vinkó Tamás  |e ths 
856 4 0 |u https://doktori.bibl.u-szeged.hu/id/eprint/12021/2/thesis.pdf  |z Dokumentum-elérés  
856 4 0 |u https://doktori.bibl.u-szeged.hu/id/eprint/12021/5/booklet.pdf  |z Dokumentum-elérés