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:20180101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20191210T163000
DTEND;TZID=Asia/Seoul:20191210T173000
DTSTAMP:20260420T165113
CREATED:20191004T104834Z
LAST-MODIFIED:20240707T084332Z
UID:1488-1575995400-1575999000@dimag.ibs.re.kr
SUMMARY:Jakub Gajarský\, First-order interpretations of bounded expansion classes
DESCRIPTION:The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular\, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs\, we introduce classes of graphs with structurally bounded expansion\, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment\, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth decompositions\, replacing treedepth by its dense analogue called shrubdepth.
URL:https://dimag.ibs.re.kr/event/2019-12-10/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR