Maximum matching width: new characterizations and a fast algorithm for dominating set

Jisu Jeong, Sigve Hortemo Sæther, Jan Arne Telle

We give alternative definitions for maximum matching width, e.g. a graph $G$ has $\mathrm{mmw}(G)\le k$ if and only if it is a subgraph of a chordal graph $H$ and for every…