Algoritmos lineares para emparelhamentos conexos máximos ponderados e não ponderados

Bruno P. Masquio, Paulo E. D. Pinto, Jayme L. Szwarcfiter

Resumo


Problemas de emparelhamentos em grafos são bem conhecidos e estudados, nos quais  desejamos determinar conjuntos de arestas não adjacentes duas a duas. Surgiu um interesse pelo  estudo do emparelhamento cujo subgrafo induzido pelos vértices do emparelhamento é conexo, o  qual pode ser estudado em grafos poderados e não ponderados. Para os não ponderados, deseja-se  obter um emparelhamento de cardinalidade máxima. Esse problema já foi identificado polinomial,  porém sua complexidade exata era desconhecida. Obtivemos um algoritmo linear que, a partir de  um emparelhamento máximo, resolve o problema para grafos gerais. Já para os ponderados, ainda  não se conhece sua complexidade para grafos gerais, porém apresentamos um algoritmo linear para  resolvê-lo para árvores.


Palavras-chave


Algoritmos; Emparelhamento; Conexo; Ponderado; Árvores.

Texto completo:

PDF

Referências


Goddard W., Hedetniemi S. M. , Hedetniemi S. T. and Laskar R. Generalized Subgraph- restricted Matchings in Graphs, Discrete Mathematics, volume 293, issues 1-3, pages 129-138, 2005. DOI: 10.1016/j.disc.2004.08.027.

Masquio, B. P. Emparelhamentos desconexos, Dissertação de Mestrado, UERJ, 2019.

Micali, S. and Vazirani, V. V. An O(-/|V||E?|) algorithm for finding maximum matching in general graphs, 21 st Annual Symposium on Foundations of Computer Science (sfcs 1980), pages 17-27, 1980. DOI: 10.1109/SFCS.1980.12.

Savage, C. Maximum matchings and trees, Information Processing Letters, volume 10, issues 4-5, pages 202-205, 1980. DOI: 10.1016/0020-0190(80)90140-4




DOI: https://doi.org/10.5540/03.2021.008.01.0354

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato