### Page Content

### to Navigation

# 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 O(`|V|`

^{3}) time and O(`|V||E|`

) time respectively.

Date | Speaker | Location | Language |
---|---|---|---|

07.07.2016 16:30 h | Leon Kellerhals | TEL 512 | English |