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.
翻译：我们首先设计一个 $\ mathcal{ O} (n% 2) 的解决方案, 以在调制图中找到最大诱导匹配值, 以其变换模型, 以动态编程算法为基础, 并借助扫描线技术。 在脱节数据结构的支持下, 我们把复杂性提高到$\ mathcal{ O}( m + n) 。 因此, 我们扩展了这个结果, 以给出 $\ m mathcal{ O} (m + n) 的算法, 来应对拖网图中的相同问题。 通过将我们的算法与当前最佳的图形识别算法相结合, 我们可以在线性 和 $\ mathcal{ O} (n% 2) 的时间中分别解决 MIM 问题。 我们的结果比 Habib et al 提出的 。
相关内容
微信扫码咨询专知VIP会员