Viet Dung Nguyen ; Ba Thai Pham ; Phan Thuan Do - Efficient algorithms for maximum induced matching problem in permutation and trapezoid graphs

fi:7684 - Fundamenta Informaticae, November 18, 2021, Volume 182, Issue 3 - https://doi.org/10.3233/FI-2021-2073
Efficient algorithms for maximum induced matching problem in permutation and trapezoid graphs

Authors: 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.


Volume: Volume 182, Issue 3
Published on: November 18, 2021
Accepted on: July 22, 2021
Submitted on: July 20, 2021
Keywords: Computer Science - Data Structures and Algorithms,Computer Science - Discrete Mathematics


Share

Consultation statistics

This page has been seen 13 times.
This article's PDF has been downloaded 100 times.