Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
Hardness and Approximation for the Geodetic Set Problem in Some Graph Classes
verfasst von : Dibyayan Chakraborty, Florent Foucaud, Harmender Gahlawat, Subir Kumar Ghosh, Bodhayan Roy
Erschienen in: Algorithms and Discrete Applied Mathematics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In this paper, we study the computational complexity of finding the geodetic number of graphs. A set of vertices S of a graph G is a geodetic set if any vertex of G lies in some shortest path between some pair of vertices from S. The Minimum Geodetic Set (MGS) problem is to find a geodetic set with minimum cardinality. In this paper, we prove that solving MGS is NP-hard on planar graphs with a maximum degree six and line graphs. We also show that unless \(P=NP\), there is no polynomial time algorithm to solve MGS with sublogarithmic approximation factor (in terms of the number of vertices) even on graphs with diameter 2. On the positive side, we give an \(O\left( \root 3 \of {n}\log n\right) \)-approximation algorithm for MGS on general graphs of order n. We also give a 3-approximation algorithm for MGS on solid grid graphs which are planar.