20.500.12556/DKUM-92014 Strong geodetic problem in networks Krepko geodetski problem na omrežjih In order to model certain social network problems, the strong geodetic problem and its related invariant, the strong geodetic number, are introduced. The problem is conceptually similar to the classical geodetic problem but seems intrinsically more difficult. The strong geodetic number is compared with the geodetic number and with the isometric path number. It is determined for several families of graphs including Apollonian networks. Applying Sierpiński graphs, an algorithm is developed that returns a minimum path cover of Apollonian networks corresponding to the strong geodetic number. It is also proved that the strong geodetic problem is NP-complete. Z namenom modeliranja določenih problemov v socialnih omrežjih je v članku vpeljan krepko geodetski problem in pripadajoča grafovska invarianta krepko geodetsko število. Problem je konceptualno podoben klasičnemu geodetskemu problemu, a se vseeno zdi intrinzično zahtevnejši. Krepko geodetsko število je primerjano z geodetskim številom in s številom izometričnih poti. Krepko geodetsko število je določeno za več družin grafov, med drugim za Apollonijeva omrežja. Z uporabo grafov Sierpińskega je razvit algoritem, ki vrne minimalno pokritje s potmi Apollonijevih omrežij, ki ustreza krepko geodetskemu številu. Dokazano je tudi, da je krepko geodetski problem NP-poln. geodetic problem strong geodetic problem Apollonian networks Sierpiński graphs computational complexity geodetski problem krepko geodetski problem Apollonijeva omrežja grafi Sierpińskega računska zahtevnost true false true Technical University Press Angleški jezik Slovenski jezik Znanstveno delo 2025-03-11 12:07:58 2025-03-11 12:25:19 2025-03-12 03:12:42 0000-00-00 00:00:00 2020 0 0 Str. 307-321 št. 1 Letn. 40 2020 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2017-07-17 2018-03-19 0000-00-00 519.17 18817113 10.7151/dmgt.2139 1234-3099 Manuel-2020-STRONG_GEODETIC_PROBLEM_IN_NETWORK.pdf Manuel-2020-STRONG_GEODETIC_PROBLEM_IN_NETWORK.pdf 1 6F794C14B4C1408FAB8D2268C065236A 108c58f8d759e81be64c602cd97af3f4d4a017349c35652007d5a1d4abca13ab 4d29fdeb-fe6b-11ef-b15e-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=189163 https://doi.org/10.7151/dmgt.2139 0 17e243b4-fe69-11ef-b15e-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=189162 Fakulteta za naravoslovje in matematiko 0 0 0