Linear MIM-Width of Trees

Svein Høgemo, Jan Arne Telle, Erlend Raa Vågset

We provide an $O(n\log n)$ algorithm computing the linear maximum induced matching width of a tree and an optimal layout.