Max-Planck-Institut für Informatik
max planck institut
informatik
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:Disjoint Paths Problem
Speaker:Saeed Amiri
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:A postdoc at MPII.
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Thursday, 11 January 2018
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
The disjoint paths problem is an extensively studied problem in graph theory and theoretical computer science and it also has important practical applications, e.g. it appears in VLSI design and various routing problems. In designing network algorithms one need to route paths through a small number of hubs, which introduces the length bounded variant of the disjoint paths problem. The disjoint paths problem also finds application in scheduling and timetabling.

The input is a graph G=(V,E) and a set of pairs of vertices {(s_1,t_1),...,(s_k,t_k)} the question is to find k paths P_1,...,P_k such that the path P_i connects s_i to t_i for i=1 to k and every pair of paths P_i,P_j are internally vertex disjoint. This also called k-disjoint paths problem. The problem is hard in general graphs, however it admits an FPT algorithm in undirected graphs. In directed graphs, the problem is much harder: it is NP-complete already for 2-disjoint paths problem.

In this talk, we provide an overview of this problem and we try to cover the state of the art. We then consider a relaxed version of this problem and explain some ideas around it, namely we focus on the disjoint paths with congestion: every vertex can route upto c paths where c is the congestion.

Contact
Name(s):Saeed Amiri
EMail:samiri@mpi-inf.mpg.de
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Keywords:Disjoint paths, directed graphs, algorithms, graph minor theorem
Note:We explain everything which is needed to understand the topic, however, a bit understanding about structural properties such as tree width might help.

If a reader is interested in the problem here are some suggestions for further reading (the graph minor XIII is very hard to read):

https://link.springer.com/chapter/10.1007/978-3-642-19094-0_2
https://www.sciencedirect.com/science/article/pii/S0095895685710064
http://drops.dagstuhl.de/opus/volltexte/2016/6424/pdf/LIPIcs-MFCS-2016-7.pdf
Attachments, File(s):

Created:
Saeed Amiri, 01/05/2018 01:18 PM
Last modified:
Uwe Brahm/MPII/DE, 01/11/2018 04:01 AM
  • Saeed Amiri, 01/05/2018 01:21 PM
  • Saeed Amiri, 01/05/2018 01:18 PM -- Created document.