Efficient maximum matching algorithms for trapezoid graphs
| Main Authors: | Do, Phan-Thuan; Department of Computer Science, Hanoi University of Science and Technology, Vietnam, Le, Ngoc-Khang; LIP, ENS de Lyon, Lyon, France, Vu, Van-Thieu; Department of Computer Science, Hanoi University of Science and Technology, Vietnam |
|---|---|
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2017
|
| Subjects: | |
| Online Access: |
http://www.ejgta.org/index.php/ejgta/article/view/273 http://www.ejgta.org/index.php/ejgta/article/view/273/pdf_32 |
Daftar Isi:
- 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.