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

Autores/as

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

DOI:

https://doi.org/10.5540/03.2021.008.01.0354

Palabras clave:

Algoritmos, Emparelhamento, Conexo, Ponderado, Árvores.

Resumen

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.

Descargas

Los datos de descargas todavía no están disponibles.

Biografía del autor/a

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

Citas

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

Publicado

2021-12-20

Número

Sección

Trabalhos Completos