Algoritmos eficientes para emparelhamentos desconexos em grafos cordais e grafos bloco
Graph matching problems are well studied and bring great contributions to Graph Theory from both the theoretical and practical points of view. There are numerous studies for unrestricted and weighted/unweighted matchings. More recently, subgraph-restricted matchings have been proposed, which consider properties of the subgraph induced by the vertices of the matching. In this paper, we approach one of these new proposals, disconnected matching, which seeks to study maximum matching, such that the subgraph induced by the matching vertices is disconnected. We have described efficient algorithms to solve the problem for chordal graphs and block graphs based on a theoretical characterization.
Fulkerson, D. R. and Gross, O. A. (1965). Incidence matrices and interval graphs. Pacific J. Math., 15(3):835–855.
Goddard, W., Hedetniemi, S. M., Hedetniemi, S. T., and Laskar, R. (2005). Generalized subgraph-restricted matchings in graphs. Discrete Math., 293(1-3):129–138.
Masquio, B. P. (2019). Emparelhamentos desconexos. Master’s thesis, Universidade do Estado do Rio de Janeiro. Disponível em https://github.com/BMasquio/papers/raw/master/MastersThesisBrunoMasquio.pdf.
Micali, S. and Vazirani, V. V. (1980). An O(sqrt(|V|)|E|) algorithm for finding maximum matching in general graphs. In 21st Ann. Symp. on Foundations ofComp. Sc., p. 17–27.