episciences.org_7684_1642654701
1642654701
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Fundamenta Informaticae
1875-8681
11
18
2021
Volume 182, Issue 3
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 with the aid of the sweep line technique. With
the 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. By
combining 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 best
known $\mathcal{O}(mn)$ algorithm for the maximum induced matching problem in
both graph classes, which was proposed by Habib et al.
11
18
2021
7684
arXiv:2107.08480
10.3233/FI-2021-2073
https://fi.episciences.org/7684