Exact geodetic number and its upper bound for random graphs

Al-Anaqreh, Ahmad (2018) Exact geodetic number and its upper bound for random graphs. Masters, Szegedi Tudományegyetem.

[thumbnail of 2018_Al_Anaqreh_Ahmad_F3MKSK_SZ.pdf] PDF
Hozzáférés joga: SZTE designated computers only

Download (929kB)
[thumbnail of 2018_al_anaqreh_ahmad.zip] Archive (ZIP)
Hozzáférés joga: SZTE designated computers only

Download (3kB)
[thumbnail of 2019_ahmad_al-anaqreh_biralati_lap.pdf] PDF
Hozzáférés joga: Repository staff only

Download (563kB)


The problem has chosen for this thesis work is coming from graph theory. It is a computationally difficult problem called geodetic number. The work was divided into two parts. In the first part we wanted to find the exact geodetic number for random graphs by using Binary Linear Programming. The model taken from the literature was tested on a large set of random graphs. These tests serve as baselines for the second part of the work. In phase two the task was to find upper bounds of the geodetic number. The computational results show that the developed upper bound schemes give perfect results with very good execution time compared to the exact results and execution time of the original linear programming model. Also, in the second part of the project we investigated the relationship between centrality values and geodetic nodes. Based on empirical observations we derived some basic rules which could be able to identify the geodetic nodes using their centrality values. Due to the high variety of the ranking of the nodes in our test graphs it was non-trivial to propose a general rule covering all the possibilities. Nevertheless, the scheme itself is worth further consideration which we plan to do in our forthcoming scientific work.


Szegedi Tudományegyetem


Faculty of Science and Informatics


Számítógépes Optimalizálás Tanszék


Natural Sciences


Informatikai Intézet


programtervező informatikus


Supervisor scientific name label
Vinkó, Tamás
associate professor

Item Type: Thesis (Masters)
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Depositing User: TTIK szerkesztő
Date Deposited: 2019. Sep. 24. 08:37
Last Modified: 2023. Nov. 08. 20:10
URI: https://diploma.bibl.u-szeged.hu/id/eprint/73810

Actions (login required)

View Item View Item