@article{EfficientMaximumMatchingAlgorithmsforTrapezoidGraphs,
author = {Phan-Thuan Do and Ngoc-Khang Le and Van-Thieu Vu},
title = {Efficient Maximum Matching Algorithms for Trapezoid Graphs},
number = {1},
volume = {5},
journal = {Electronic Journal of Graph Theory and Applications},
year = {2017},
abstract = {Trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. Many NP-hard problems can be solved in polynomial time if they are restricted on trapezoid graphs. A matching in a graph is a set of pairwise disjoint edges, and a maximum matching is a matching of maximum size. In this paper, we first propose an $O(n(\log n)^3)$ algorithm for finding a maximum matching in trapezoid graphs, then improve the complexity to $O(n(\log n)^2)$. Finally, we generalize this algorithm to a larger graph class, namely $k$-trapezoid graphs. To the best of our knowledge, these are the first efficient maximum matching algorithms for trapezoid graphs.},
pages = {7--20},
}