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

Research paper by Mauro Mezzini

Indexed on: 07 Jun '18Published on: 03 Jun '18Published in: Theoretical Computer Science


Publication date: Available online 1 June 2018 Source:Theoretical Computer Science Author(s): Mauro Mezzini Given a graph G and a pair of vertices u , v the interval I G [ u , v ] 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 I G [ X ] 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.