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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220218T100000
DTEND;TZID=Asia/Seoul:20220218T110000
DTSTAMP:20260419T165632
CREATED:20220218T010000Z
LAST-MODIFIED:20240705T174212Z
UID:5154-1645178400-1645182000@dimag.ibs.re.kr
SUMMARY:Manuel Lafond\, Recognizing k-leaf powers in polynomial time\, for constant k
DESCRIPTION:A graph G is a k-leaf power if there exists a tree T whose leaf set is V(G)\, and such that uv is an edge if and only if the distance between u and v in T is at most k. The graph classes of k-leaf powers have several applications in computational biology\, but recognizing them has remained a challenging algorithmic problem for the past two decades. In a recent paper presented at SODA22\, it was shown that k-leaf powers can be recognized in polynomial time if k is fixed. \nIn this seminar\, I will present the algorithm that decides whether a graph G is a k-leaf power in time $O(n^{f(k)})$ for some function f that depends only on k (but has the growth rate of a power tower function). More specifically\, I will discuss how the difficult k-leaf power instances contain many cutsets that have the same neighborhood layering. I will then show that these similar cutsets are redundant and that removing one of them does not lose any information\, which can be exploited for algorithmic purposes.
URL:https://dimag.ibs.re.kr/event/2022-02-18/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR