Người báo cáo: Nguyễn Việt Hà
Thời gian: 9h30, Thứ 5, ngày 19 tháng 11, năm 2015
Địa điểm: Phòng 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: A matching of a graph G is a subgraph of G which its all edges have no common vertex. An algorithm of finding a maximum matching on general graph takes time O(n^3). We have studied on Distance Hereditary Graph and constructed an O(n) time algorithm of finding maximum matching on this graph. Distance Hereditary Graph is a class of graph whose structure is constructed by using Split decomposition. In the coming seminar, we will give an introduction of Split decomposition, and present our main result, which is a linear time algorithm of finding maximum matching on Distance Hereditary Graph. |
