direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.


16:30 h
Leon Kellerhals
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras