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

Authors

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

DOI:

https://doi.org/10.5540/03.2021.008.01.0354

Keywords:

Algoritmos, Emparelhamento, Conexo, Ponderado, Árvores.

Abstract

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.

Downloads

Download data is not yet available.

Author Biographies

Bruno P. Masquio

UERJ, Rio de Janeiro, RJ

Paulo E. D. Pinto

UERJ, Rio de Janeiro, RJ

Jayme L. Szwarcfiter

UFRJ/UERJ, Rio de Janeiro, RJ

References

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

Published

2021-12-20

Issue

Section

Trabalhos Completos