On the Linear MIM-width of Trees
Master thesis
Permanent lenke
https://hdl.handle.net/1956/20432Utgivelsesdato
2019-06-26Metadata
Vis full innførselSamlinger
- Master theses [217]
Sammendrag
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.