Loading Events

« All Events

  • This event has passed.
:

Nick Brettell, On the graph width parameter mim-width

Wednesday, August 26, 2020 @ 10:30 AM - 11:30 AM KST

Zoom ID: 934 3222 0374 (ibsdimag)

Speaker

Nick Brettell
Victoria University of Wellington
http://nickbrettell.com

Maximum induced matching width, also known as mim-width, is a width parameter for graphs introduced by Vatshelle in 2012.  This parameter can be defined over branch decompositions of a graph G, where the width of a vertex partition (X,Y) in G is the size of a maximum induced matching in the bipartite graph induced by edges of G with one endpoint in X and one endpoint in Y.  In this talk, I will present a quick overview of mim-width and some key results that highlight why this parameter is of interest from both a theoretical and algorithmic point of view.  I will discuss some recent work regarding the boundedness or unboundedness of mim-width for hereditary classes defined by forbidding one or two induced subgraphs, and for generalisations of convex graphs.  I will also touch on some interesting applications of this work, in particular for colouring and list-colouring.  This is joint work with Jake Horsfield, Andrea Munaro, Giacomo Paesani, and Daniel Paulusma.

Details

Date:
Wednesday, August 26, 2020
Time:
10:30 AM - 11:30 AM KST
Event Category:
Event Tags:

Venue

Zoom ID: 934 3222 0374 (ibsdimag)

Organizer

O-joung Kwon (권오정)
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.