Este trabalho foi publicado pelo Galoá e tem um DOI depositado. Para citar este trabalho, use um dos padrões abaixo:
Caso você seja um dos co-autores e queira cadastrar esse trabalho no seu Currículo Lattes, use o seguinte código: doi > 10.59254/sbpo-2020-122539
Se você NUNCA registrou um DOI no seu Lattes, veja nosso tutorial!Algoritmos lineares para emparelhamentos conexos
Bruno Porto Masquio
UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
Agora você poderia compartilhar comigo suas dúvidas, observações e parabenizações
Crie um tópicoProblemas 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.
Com ~200 mil publicações revisadas por pesquisadores do mundo todo, o Galoá impulsiona cientistas na descoberta de pesquisas de ponta por meio de nossa plataforma indexada.
Confira nossos produtos e como podemos ajudá-lo a dar mais alcance para sua pesquisa:
Esse proceedings é identificado por um DOI , para usar em citações ou referências bibliográficas. Atenção: este não é um DOI para o jornal e, como tal, não pode ser usado em Lattes para identificar um trabalho específico.
Verifique o link "Como citar" na página do trabalho, para ver como citar corretamente o artigo