BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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:20240101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20251209T163000
DTEND;TZID=Asia/Seoul:20251209T173000
DTSTAMP:20260416T090825
CREATED:20250716T135828Z
LAST-MODIFIED:20251031T171121Z
UID:11244-1765297800-1765301400@dimag.ibs.re.kr
SUMMARY:Tuukka Korhonen\, Dynamic Treewidth in Logarithmic Time
DESCRIPTION:We present a dynamic data structure that maintains a tree decomposition of width at most 9k+8 of a dynamic graph with treewidth at most k\, which is updated by edge insertions and deletions. The amortized update time of our data structure is $2^{O(k)} \log n$\, where n is the number of vertices. The data structure also supports maintaining any “dynamic programming scheme” on the tree decomposition\, providing\, for example\, a dynamic version of Courcelle’s theorem with $O_k(\log n)$ amortized update time; the $O_k(⋅)$ notation hides factors that depend on k. This improves upon a result of Korhonen\, Majewski\, Nadara\, Pilipczuk\, and Sokołowski [FOCS 2023]\, who gave a similar data structure but with amortized update time $2^{k^{O(1)}} n^{o(1)}$. Furthermore\, our data structure is arguably simpler. Our main novel idea is to maintain a tree decomposition that is “downwards well-linked”\, which allows us to implement local rotations and analysis similar to those for splay trees. \nThis talk is based on arXiv:2504.02790.
URL:https://dimag.ibs.re.kr/event/2025-12-09/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR