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

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.