MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Maximum Disjoint Paths: New Algorithms based on Tree-Likeness

Krzysztof Fleszar
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5  
AG Audience
English

Date, Time and Location

Thursday, 10 August 2017
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

Maximum Edge Disjoint Paths is a classical NP-hard problem of finding a maximum-size subset from a given set of k terminal pairs that can be routed via edge-disjoint paths. One of the big open problems in approximation algorithms is to close the gap between the best known approximation upper and lower bound.


In this talk, I introduce the problem and present new approximation algorithms (ESA 2016) that strengthen best-known results. They provide new bounds formulated in terms of the feedback vertex set number r of a graph, which measures its vertex deletion distance to a forest.

Contact

Antonios Antoniadis
--email hidden
passcode not visible
logged in users only

Krzysztof Fleszar, 07/14/2017 14:39
Antonios Antoniadis, 06/19/2017 15:50 -- Created document.