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:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210521T170000
DTEND;TZID=Asia/Seoul:20210521T180000
DTSTAMP:20260420T111505
CREATED:20210319T050153Z
LAST-MODIFIED:20240705T190024Z
UID:3818-1621616400-1621620000@dimag.ibs.re.kr
SUMMARY:Benjamin Bumpus\, Directed branch-width: A directed analogue of tree-width
DESCRIPTION:Many problems that are NP-hard in general become tractable on `structurally recursive’ graph classes. For example\, consider classes of bounded tree- or clique-width. Since the 1990s\, many directed analogues of tree-width have been proposed. However\, many natural problems (e.g. directed HamiltonPath and MaxCut) remain intractable on such digraph classes of `bounded width’. \nIn this talk\, I will introduce a new tree-width analogue for digraphs called directed branch-width which allows us to define digraph classes for which many problems (including directed HamiltonPath and MaxCut)  become linear-time solvable. Furthermore\, via the definition of directed branch-width\, I will obtain a generalisation to digraphs of Gurski and Wanke’s characterization of graph classes of bounded tree-width in terms of their line graphs. \nThis is joint work with Kitty Meeks and William Pettersson.
URL:https://dimag.ibs.re.kr/event/2021-05-21/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR