Minimum Eccentricity Shortest Paths in some Structured Graph Classes
Vol. 20, no. 2, pp. 299-322, 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 NP-hard in general graphs, we demonstrate that a minimum eccentricity shortest path can be found in linear time for distance-hereditary 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 tree-length, and graphs with bounded hyperbolicity. Additionally, we give a simple algorithm to compute an additive approximation for graphs with bounded tree-length and graphs with bounded hyperbolicity.
Submitted: November 2015.
Accepted: April 2016.
Final: April 2016.
Published: April 2016.
Communicated by Giuseppe Liotta
article (PDF)