On the Linear MIM-width of Trees
Master thesis
View/ Open
Date
2019-06-26Metadata
Show full item recordCollections
- Master theses [197]
Abstract
Linear MIM-width, and its generalization MIM-width, is a graph width parameter that has become noted for having bounded value on several important graph classes, e.g. interval graphs and permutation graphs. The linear MIM-width of a graph G measures a min-max relation on all maximum induced matchings in bipartite graphs given by a linear layout of the vertices in G, over all possible linear layouts. In this thesis we give an overlook of some of the research that has been done on this parameter, and provide a new result, computing the linear MIM-width of trees in n log n time.