Emparelhamentos desconexos

• Ano de defesa: 2019
• Autor(a) principal: Masquio, Bruno Porto
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade do Estado do Rio de Janeiro; Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística; BR; UERJ; Programa de Pós-Graduação em Ciências Computacionais
• Palavras-chave em Português: Algorithms; Block Graphs; Disconnected Matching; Matching; Split Graphs; Chordal Graphs; Trees; Minimal separators; Algoritmos; Árvores; Emparelhamento; Emparelhamento Desconexo; Grafo Bloco; Grafo Split; Grafo Cordal; Separadores minimais; Grafos - Teoria; Algoritimos; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://www.bdtd.uerj.br/handle/1/7663

A determinação de emparelhamentos máximos em grafos corresponde a problemas há muito tempo estudados e que trazem grandes contribuições à Teoria de Grafos, tanto do ponto de vista teórico quanto prático. Como tradição, 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 tais que os subgrafos induzidos pelos vértices dos emparelhamentos sejam desconexos. Conseguimos resolver o problema para classes simples de grafos tais como caminhos, ciclos, completos. Além disso, também obtivemos resultados para grafos split, árvores, grafos bloco e grafos cordais. Para essas três últimas classes, apresentamos uma base teórica que inclui teoremas de caracterizações, assim como três novos algoritmos. O trabalho também inclui um quarto algoritmo que determina um emparelhamento máximo para grafos bloco em tempo linear