Speaker: Le Ngoc Khang
Time: 9h30 Thursday, 13/03/2014
Location: Room 201 (or 301), Building A5, Institute of Mathematics, 18 Hoang Quoc Viet, Ha Noi
Abstract: Trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. Many graph problems that are NP-hard in general case have polyno- mial time algorithms for trapezoid graphs. A matching in a graph is a set of pairwise non-adjacent edges, and a maximum matching is a matching whose cardinality is maximum. In this paper, we first propose an efficient algorithm for finding a maximum matching on trapezoid graphs, then improve to get bet- ter time complexity. Finally, we generalize the algorithm for a larger graph class, k-trapezoid graphs. To the best of our knowledge, this is the first efficient maximum matching algorithm for trapezoid graphs. |
