Người báo cáo: Le Ngoc Khang
Thời gian: 9h30, thứ 5, ngày 13/3/2014
Địa điểm: Phòng 301 (hoặc 201), nhà A5, Viện Toán học, 18 Hoàng Quốc Việt, Cầu Giấy, Hà Nội
Tóm tắt: 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. |
