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:Congestion Free Rerouting of Flows (practice talk for ICALP)
Speaker:Saeed Amiri
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 3 July 2018
Duration:30 Minutes
Building:E1 4
Changing a given configuration in a graph into another one is known as a reconfiguration problem. Such problems have recently received much interest in the context of algorithmic graph theory.

We initiate the theoretical study of the following reconfiguration problem:
How to reroute $k$ unsplittable flows of a certain demand in a capacitated network from their current paths to their respective new paths, in a congestion-free manner?
This problem finds immediate applications, e.g., in traffic engineering in computer networks.
We show that the problem is generally NP-hard already for $k=2$ flows, which motivates us to study rerouting on a most basic class of flow graphs, namely DAGs. Interestingly, we find that for general $k$, deciding whether an unsplittable multi-commodity flow rerouting schedule exists, is NP-hard even on DAGs. Our main contribution is a polynomial-time (fixed parameter tractable) algorithm to solve the route update problem for a bounded number of flows on DAGs. At the heart of our algorithm lies a novel decomposition of the flow network that allows us to express and resolve reconfiguration dependencies among flows.

Name(s):Saeed Amiri
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Keywords:reconfiguration, algorithm, FPT, flow, rerouting
Note:If you like to have a quick look, you can find the early version of the paper here:
Attachments, File(s):

Created:Saeed Amiri, 06/04/2018 10:35 AM Last modified:Uwe Brahm/MPII/DE, 06/06/2018 07:01 AM
  • Saeed Amiri, 06/04/2018 10:35 AM -- Created document.