Koç University, Mathematics Seminar

Date & Time: Thursday, December 17, 16:00-17:00

Place: ENG B-05

Speaker: Tınaz Ekim (Boğaziçi University)

Title: Minimum Maximal Matching problem and Equimatchable graphs

Abstract: Given a graph, the problem of finding the minimum size maximal matching (MMM) is also known as the (independent) edge dominating set (EDS) in the literature. We will give several results about the hardness of solving MMM in special graph classes and point out some future research questions in this direction. We will also talk about the related notion of equimatchable graphs: a graph is equimatchable if all maximal matchings of it have the same size. We will discuss about the structural properties of equimatchable graphs and point out interesting open questions in this area.

Speaker's Brief Biography: Dr. Tınaz Ekim is Associate Professor at Boğaziçi Univeristy, Industrial Engineering Department. She holds B.S. degrees in Mathematics at University of Technology and Science of Lille (France, 1999) and in Industrial Engineering at Galatasaray University (2001). She completed her MS and PhD in Operations Research at respectively Dauphine University (France) in 2002 and Swiss Federal Institute of Technology at Lausanne in 2006. Her research focus is on algorithmic and structural graph theory, combinatorial optimization and computational complexity.