| Title: | Strong geodetic problem in networks |
|---|
| Authors: | ID Manuel, Paul (Author)
ID Klavžar, Sandi (Author)
ID Xavier, Antony (Author)
ID Arokiaraj, Andrew (Author)
ID Thomas, Elizabeth (Author) |
|---|
| Files: |  Manuel-2020-STRONG_GEODETIC_PROBLEM_IN_NETWORK.pdf (162,66 KB)
MD5: 6F794C14B4C1408FAB8D2268C065236A
 https://doi.org/10.7151/dmgt.2139
|
|---|
| Language: | English |
|---|
| Work type: | Scientific work |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | geodetic problem, strong geodetic problem, Apollonian networks, Sierpiński graphs, computational complexity |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Submitted for review: | 17.07.2017 |
|---|
| Article acceptance date: | 19.03.2018 |
|---|
| Publisher: | Technical University Press |
|---|
| Year of publishing: | 2020 |
|---|
| Number of pages: | Str. 307-321 |
|---|
| Numbering: | Letn. 40, št. 1 |
|---|
| PID: | 20.500.12556/DKUM-92014  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 1234-3099 |
|---|
| COBISS.SI-ID: | 18817113 |
|---|
| DOI: | 10.7151/dmgt.2139 |
|---|
| Publication date in DKUM: | 11.03.2025 |
|---|
| Views: | 103 |
|---|
| Downloads: | 7 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
