Emparelhamentos Desconexos em Grafos Cordais e Subclasses

Os problemas de emparelhamentos máximos em grafos são bem estudados e trazem grandes contribuições à Teoria de Grafos, tanto do ponto de vista teórico quanto prático. Há numerosos estudos na área, destinados a emparelhamentos irrestritos e sem pesos. Mais recentemente, foram propostos os emparelhamentos restritos a subgrafos, que consideram propriedades dos subgrafos induzidos pelos vértices do emparelhamento. Neste trabalho, abordamos uma dessas novas propostas, que são os emparelhamentos desconexos, os quais procuram estudar emparelhamentos máximos tais que o subgrafo induzido pelos vértices do emparelhamento seja desconexo. Descrevemos algoritmos eficientes para resolver o problema em grafos cordais e subclasses, baseados em caracterizações teóricas. O algoritmo de grafos cordais tem complexidade de tempo O(nm) e, além disso, foi possível uma redução para complexidade linear em algumas subclasses, tais como árvores e grafos bloco.