Time: 9h30, Thursday, November 19, 2015
Location: Room 201 Building A5, Institute of Mathematics
Abstract:  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.