Open AccessAlgoritmos eficientes para emparelhamentos desconexos em grafos cordais e grafos bloco
Author(s) -
Bruno P. Masquio,
Paulo E. D. Pinto,
Jayme Luiz Szwarcfiter
Publication year - 2019
Language(s) - English
Resource type - Conference proceedings
DOI - 10.5753/etc.2019.6390
Subject(s) - combinatorics , matching (statistics) , factor critical graph , mathematics , graph factorization , chordal graph , induced subgraph , graph , computer science , distance hereditary graph , discrete mathematics , theoretical computer science , line graph , graph power , statistics , vertex (graph theory)
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.