Algoritmos lineares para emparelhamentos conexos

Favorite this paper
How to cite this paper?
Details
  • Presentation type: Trabalho completo (oral)
  • Track: 19. TAG – Teoria e Algoritmos em Grafos
  • Keywords: 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

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. 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.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!