Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
| Autor: | Ba Thai Pham, Viet Dung Nguyen, Phan Thuan Do |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Algebra and Number Theory Current (mathematics) Discrete Mathematics (cs.DM) Matching (graph theory) Efficient algorithm Trapezoid graph Data structure Theoretical Computer Science Sweep line algorithm Dynamic programming Combinatorics Permutation Computational Theory and Mathematics Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) Computer Science - Discrete Mathematics MathematicsofComputing_DISCRETEMATHEMATICS Information Systems Mathematics |
| Zdroj: | Fundamenta Informaticae. 182:257-283 |
| ISSN: | 1875-8681 0169-2968 |
| DOI: | 10.3233/fi-2021-2073 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|