| Autor: |
Lima, Carlos V.G.C., dos Santos, Vinicius F., Sousa, Joãao H.G., Urrutia, Sebastián A. |
| Předmět: |
|
| Zdroj: |
RAIRO: Operations Research (2804-7303); 2024, Vol. 58 Issue 5, p3755-3770, 16p |
| Abstrakt: |
A strong geodetic set of a graph G = (V, E) is a vertex set S⊆V (G) in which it is possible to cover all the remaining vertices of V (G) ∖S by assigning a unique shortest path between each vertex pair of S. In the Strong Geodetic problem (SG) a graph G and a positive integer k are given as input and one has to decide whether G has a strong geodetic set of cardinality at most k. This problem is known to be NP-hard for general graphs. In this work we introduce the Strong Geodetic Recognition problem (SGR), which consists in determining whether a given vertex set S⊆V (G) is strong geodetic. We demonstrate that this version is NP-complete. We investigate and compare the computational complexity of both decision problems restricted to some graph classes, deriving polynomial-time algorithms, NP-completeness proofs, and initial parameterized complexity results, including an answer to an open question in the literature for the complexity of SG for chordal graphs. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
