Loading Events

« All Events

  • This event has passed.
:

Nick Brettell, On the graph width parameter mim-width

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

Zoom

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:
August 26 Wednesday
Time:
10:30 AM - 11:30 AM KST
Event Category:
Event Tags:

Venue

Zoom

Organizer

O-joung Kwon (권오정)