Research Group Algorithmics and Computational ComplexityTalk 07.07.2016

# 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

Back to the research colloquium site.