- Tytuł:
- Strong Geodetic Problem in Networks
- Autorzy:
-
Manuel, Paul
Klavžar, Sandi
Xavier, Antony
Arokiaraj, Andrew
Thomas, Elizabeth - Powiązania:
- https://bibliotekanauki.pl/articles/32083731.pdf
- Data publikacji:
- 2020-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
geodetic problem
strong geodetic problem
Apollonian networks
Sierpiński graphs
computational complexity - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 307-321
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł