Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Maximum Disjoint Paths: New Algorithms based on Tree-Likeness
Speaker:Krzysztof Fleszar
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 10 August 2017
Duration:30 Minutes
Building:E1 4
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.

Name(s):Antonios Antoniadis
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Antonios Antoniadis, 06/19/2017 03:50 PM
Last modified:
halma/MPII/DE, 01/17/2019 12:04 AM
  • Krzysztof Fleszar, 07/14/2017 02:39 PM
  • Antonios Antoniadis, 06/19/2017 03:50 PM -- Created document.