Algoritmos lineares para emparelhamentos conexos

Favoritar este trabalho
Como citar esse trabalho?
Detalhes
  • Tipo de apresentação: Trabalho completo (oral)
  • Eixo temático: 19. TAG – Teoria e Algoritmos em Grafos
  • Palavras chaves: Emparelhamento; Conexo; Ponderado;
  • 1 UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
  • 2 Universidade Federal do Rio de Janeiro

Algoritmos lineares para emparelhamentos conexos

Bruno Porto Masquio

UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO

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. Este trabalho se dedica ao estudo do emparelhamento cujos subgrafos induzidos pelos vértices do emparelhamento são conexos ou desconexos. Podemos considerar também grafos poderados e não ponderados. Para os não ponderados, deseja-se obter um emparelhamento de cardinalidade máxima, enquanto que para os ponderados o objetivo é determinar um emparelhamento cuja soma dos pesos das arestas do emparelhamento é máxima. Enquanto conjecturamos que o problema de emparelhamento desconexo máximo é NP-completo, o problema de emparelhamento conexo máximo é polinomial. Mostramos um algoritmo linear que, a partir de um emparelhamento máximo, determina um emparelhamento conexo máximo. Para emparelhamento conexo ponderado, sua complexidade ainda é desconhecida para grafos gerais. Entretanto, apresentamos um algoritmo linear para resolvê-lo para árvores.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!