Efficient Maximum Matching Algorithms for Trapezoid Graphs
2017
Phan-Thuan Do, Ngoc-Khang Le, Van-Thieu Vu

Metrics

  • Eye Icon 268 views
  • Download Icon 77 downloads
Metrics Icon 268 views  //  77 downloads
Efficient Maximum Matching Algorithms for Trapezoid Graphs Image
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.

Full text
Show more arrow
 
More from this journal
Graphs Obtained From Collections of Blocks
Graphs Obtained From Collections of Blocks Image
On Maximum Signless Laplacian Estrada Index of Graphs with Given Parameters II
On Maximum Signless Laplacian Estrada Index of Graphs with Given Parameters II Image
Some Diameter Notions in Lexicographic Product
Some Diameter Notions in Lexicographic Product Image
🧐  Browse all from this journal

Metrics

  • Eye Icon 268 views
  • Download Icon 77 downloads
Metrics Icon 268 views  //  77 downloads