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

We first design an $\mathcal{O}(n^2)$ solution for finding a maximum inducedmatching in permutation graphs given their permutation models, based on adynamic programming algorithm with the aid of the sweep line technique. Withthe support of the disjoint-set data structure, we improve the complexity to$\mathcal{O}(m + n)$. Consequently, we extend this result to give an$\mathcal{O}(m + n)$ algorithm for the same problem in trapezoid graphs. Bycombining our algorithms with the current best graph identification algorithms,we can solve the MIM problem in permutation and trapezoid graphs in linear and$\mathcal{O}(n^2)$ time, respectively. Our results are far better than the bestknown $\mathcal{O}(mn)$ algorithm for the maximum induced matching problem inboth graph classes, which was proposed by Habib et al