Modeling and Optimizing for NP-hard Problems in Graph Theory

Anaqreh Ahmad
Modeling and Optimizing for NP-hard Problems in Graph Theory.
Doctoral thesis (PhD), University of Szeged.
(2024)

[thumbnail of thesis.pdf] PDF (thesis)
Download (1MB)
[thumbnail of booklet.pdf] PDF (booklet)
Download (1MB)

Abstract in Hungarian

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.

Abstract in foreign language

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.

Item Type: Thesis (Doctoral thesis (PhD))
Creators: Anaqreh Ahmad
Hungarian title: Modellezés és optimalizálás NP-nehez problémákhoz gráfelméletben
Supervisor(s):
Supervisor
Position, academic title, institution
MTMT author ID
Gazdag-Tóth Boglárka
tudományos főmunkatárs, Számítógépes Optimalizálás Tanszék SZTE / TTIK / INF
10002021
Vinkó Tamás
egyetemi docens, Számítógépes Optimalizálás Tanszék SZTE / TTIK / INF
10022652
Subjects: 01. Natural sciences > 01.02. Computer and information sciences
Divisions: Doctoral School of Computer Science
Discipline: Engineering > Information Technology
Language: English
Date: 2024. May 10.
Item ID: 12021
Date Deposited: 2024. Jan. 09. 13:21
Last Modified: 2024. Apr. 17. 12:07
Depository no.: B 7397
URI: https://doktori.bibl.u-szeged.hu/id/eprint/12021
Defence/Citable status: Not Defended. (Do not cite until it has not assigned DOI number!)

Actions (login required)

View Item View Item