On the Minimum Eccentricity Shortest Path Problem
Leon Kellerhals (TU Berlin)
F. Dragan and A. Leitert [WADS 2015] introduced the Minimum Eccentricity Shortest Path (MESP) problem , which is defined as follows: Given a graph G=(V,E), out of all shortest paths, find a path P with minimum eccentricity, that is, find a path P for which the distance to the most distant vertex in G from P is the smallest. The problem is NP-hard on general graphs.
In this talk, I will present their results, focusing on
- how MESP can be used to obtain the best to date approximation algorithm for a minimum distortion embedding from a graph to a line,
- their linear-time algorithm for MESP on trees, and
- their 2-approximation and 3-approximation algorithms for MESP in
|V|3) time and
Back to the research colloquium site.