Department Seminars & Colloquia

Category IBS-KAIST Seminar
Event Discrete Mathematics
Title Parameterized algorithms for the planar disjoint paths problem
Abstract Given an undirected planar graph $G$ with $n$ vertices and a set $T$ of $k$ pairs $(s_i,t_i)_{i=1}^k$ of vertices, the goal of the planar disjoint paths problem is to find a set $\mathcal P$ of $k$ pairwise vertex-disjoint paths connecting $s_i$ and $t_i$ for all indices $i\in\{1,\ldots,k\}$. This problem has been studied extensively due to its numerous applications such as VLSI layout and circuit routing. However, this problem is NP-complete even for grid graphs. This motivates the study of this problem from the viewpoint of parameterized algorithms. In this talk, I will present a $2^{O(k^2)}n$-time algorithm for the planar disjoint paths problem. This improves the two previously best-known algorithms: $2^{2^{O(k)}}n$-time algorithm [Discrete Applied Mathematics 1995] and $2^{O(k^2)}n^6$-time algorithm [STOC 2020]. This is joint work with Kyungjin Cho and Seunghyeok Oh.
Daytime 2023-03-07 (Tue) / 16:30 ~ 17:30
Place Room B332, IBS (기초과학연구원)
Language English
Speaker`s name Eunjin Oh
Speakers`s Affiliation POSTECH
Speaker`s homepage https://sites.google.com/view/eunjinoh/
Other information
Hosts Sang-il Oum
URL https://dimag.ibs.re.kr/event/2023-03-07/
담당자
연락처