[KAIST Discrete Math Seminar] Colloquium: 11/26 THU 4:30PM (Ken-ichi Kawarabayashi, National Institute of Informatics)

[Sang-il Oum]

FYI: A colloquium talk next week at KAIST will be a topic related to
KAIST Discrete Math Seminar.
Ken-ichi Kawarabayashi will also give another talk on Nov. 24, Tuesday 4PM.

***** COLLOQUIUM *****

DATE: Nov. 26, Thursday

TIME: 4:30PM-5:30PM

PLACE: E6-1, ROOM 1501

SPEAKER: Ken-ichi Kawarabayashi, National Institute of Informatics, Tokyo

TITLE: The disjoint paths problem: Algorithm and Structure

http://mathsci.kaist.ac.kr/~sangil/seminar/entry/20091126/

In this talk, we shall discuss the following well-known problem, which
is called the disjoint paths problem.

Given a graph G with n vertices and m edges, k pairs of vertices
(s1,t1),(s2,t2),…,(sk,tk) in G (which are sometimes called terminals).
Are there disjoint paths P1,…,Pk in G such that Pi joins si and ti for
i=1,2,…,k?

We discuss recent progress on this topic, including algorithmic aspect
of the disjoint paths problem.

We also discuss some structure theorems without the k disjoint paths.
Topics include the uniquely linkage problem and the connectivity
function that guarantees the existence of the k disjoint paths.