BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230307T163000
DTEND;TZID=Asia/Seoul:20230307T173000
DTSTAMP:20260419T131159
CREATED:20230111T063520Z
LAST-MODIFIED:20240707T074009Z
UID:6655-1678206600-1678210200@dimag.ibs.re.kr
SUMMARY:Eunjin Oh (오은진)\, Parameterized algorithms for the planar disjoint paths problem
DESCRIPTION: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. \nIn 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]. \nThis is joint work with Kyungjin Cho and Seunghyeok Oh.
URL:https://dimag.ibs.re.kr/event/2023-03-07/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR