Given a graph G and a pair of vertices the interval is the set of all vertices that are in some shortest path between u and v. Given a subset X of vertices of G, the interval of X, is the union of the intervals for all pairs of vertices in X and we say that X is geodetic if its interval do coincide with the set of vertices in the graph. A minimum geodetic set is a minimum cardinality geodetic set of G. The problem of computing a minimum geodetic set is known to be NP-Hard for general graphs but is known to be polynomially solvable for maximal outerplanar graphs. In this paper we show a polynomial time algorithm for finding a minimum geodetic set in general outerplanar graphs.

Mezzini, M. (2018). Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs. THEORETICAL COMPUTER SCIENCE [10.1016/j.tcs.2018.05.032].

Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs

Mauro Mezzini
2018-01-01

Abstract

Given a graph G and a pair of vertices the interval is the set of all vertices that are in some shortest path between u and v. Given a subset X of vertices of G, the interval of X, is the union of the intervals for all pairs of vertices in X and we say that X is geodetic if its interval do coincide with the set of vertices in the graph. A minimum geodetic set is a minimum cardinality geodetic set of G. The problem of computing a minimum geodetic set is known to be NP-Hard for general graphs but is known to be polynomially solvable for maximal outerplanar graphs. In this paper we show a polynomial time algorithm for finding a minimum geodetic set in general outerplanar graphs.
2018
Mezzini, M. (2018). Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs. THEORETICAL COMPUTER SCIENCE [10.1016/j.tcs.2018.05.032].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/338384
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 8
social impact