TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 07.07.2016

isti-logo

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

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe