Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00394
Minimum Eccentricity Shortest Paths in some Structured Graph Classes
Vol. 20, no. 2, pp. 299322, 2016. Regular paper.
Abstract We investigate the Minimum Eccentricity Shortest Path problem in some structured graph classes. It asks for a given graph to find a shortest path with minimum eccentricity. Although it is NPhard in general graphs, we demonstrate that a minimum eccentricity shortest path can be found in linear time for distancehereditary graphs (generalizing the previous result for trees) and give a generalised approach which allows to solve the problem in polynomial time for other graph classes. This includes chordal graphs, dually chordal graphs, graphs with bounded treelength, and graphs with bounded hyperbolicity. Additionally, we give a simple algorithm to compute an additive approximation for graphs with bounded treelength and graphs with bounded hyperbolicity.

Submitted: November 2015.
Accepted: April 2016.
Final: April 2016.
Published: April 2016.
Communicated by
Giuseppe Liotta
