Loading Events

« All Events

  • This event has passed.
:

Benjamin Bumpus, Directed branch-width: A directed analogue of tree-width

Friday, May 21, 2021 @ 5:00 PM - 6:00 PM KST

Zoom ID: 869 4632 6610 (ibsdimag)

Speaker

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’.

In 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.

This is joint work with Kitty Meeks and William Pettersson.

Details

Date:
Friday, May 21, 2021
Time:
5:00 PM - 6:00 PM KST
Event Category:
Event Tags:

Venue

Zoom ID: 869 4632 6610 (ibsdimag)
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.