10.3233/FI-2021-2073
Nguyen, Viet Dung
Viet Dung
Nguyen
Pham, Ba Thai
Ba Thai
Pham
Do, Phan Thuan
Phan Thuan
Do
Efficient algorithms for maximum induced matching problem in permutation
and trapezoid graphs
episciences.org
2021
Computer Science - Data Structures and Algorithms
Computer Science - Discrete Mathematics
contact@episciences.org
episciences.org
2021-07-20T04:17:56+02:00
2021-11-18T11:14:08+01:00
2021-11-18
eng
Journal article
https://fi.episciences.org/7684
arXiv:2107.08480
1875-8681
PDF
1
Fundamenta Informaticae ; Volume 182, Issue 3 ; 1875-8681
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.