max planck institut

informatik

informatik

<< Previous Entry | Next Entry >> | New Event Entry | Edit this Entry | Login to DB (to update, delete) |

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: | Thursday, 11 January 2018 |
---|---|

Time: | 13:00 |

Duration: | 30 Minutes |

Location: | Saarbrücken |

Building: | E1 4 |

Room: | 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. |

Name(s): | Saeed Amiri |
---|---|

EMail: | samiri@mpi-inf.mpg.de |

Video Broadcast: | No | To Location: |
---|

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.