max planck institut
informatik

# 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)
Title: Disjoint Paths Problem Saeed Amiri Max-Planck-Institut für Informatik - D1 A postdoc at MPII. AG1 Mittagsseminar (own work) D1We use this to send out email in the morning. AG Audience English
Date: Thursday, 11 January 2018 13:00 30 Minutes Saarbrücken E1 4 024
 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.
Name(s): Saeed Amiri samiri@mpi-inf.mpg.de