Emparelhamentos Conexos - Masquio, Bruno P.; Pinto, Paulo E. D.; Szwarcfiter, Jayme L. (Anais do Encontro de Teoria da Computação (ETC); 2020: Anais do V Encontro de Teoria da Computação, 2020)
Graph matching problems are well known and studied, in which we want to find sets of pairwise non-adjacent edges. Recently, there has been an interest in the study of matchings in which the induced subgraphs by the vertices of matchings are connected or disconnected. Although these problems are related to connectivity, the two problems are probably quite different, regarding their complexity. While the complexity of finding a maximum disconnected mat- ching is still unknown for a general graph, the one for connected matchings can be solved in polynomial time. Our contribution in this paper is a linear time algorithm to find a maximum connected matching of a general connected graph, given a general maximum matching as input.