Efficient algorithms for maximum induced matching problem in permutation and trapezoid graphs

Viet Dung Nguyen, Ba Thai Pham, Phan Thuan Do

We first design an $\mathcal{O}(n^2)$ solution for finding a maximum induced matching in permutation graphs given their permutation models, based on a dynamic programming algorithm…