This paper was published through Galoá and has a deposited DOI. To cite this paper, use one of the standards below:
In case you are one of the co-authors and want to register this paper in your Lattes, use the following code: doi > 10.59254/sbpo-2020-122539
If you've NEVER registered a DOI in your Lattes, check our tutorial!Algoritmos lineares para emparelhamentos conexos
Bruno Porto Masquio
UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
Now you could share with me your questions, observations and congratulations
Create a topicWatch this next:
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.
With nearly 200,000 papers published, Galoá empowers scholars to share and discover cutting-edge research through our streamlined and accessible academic publishing platform.
Learn more about our products:
This proceedings is identified by a DOI , for use in citations or bibliographic references. Attention: this is not a DOI for the paper and as such cannot be used in Lattes to identify a particular work.
Check the link "How to cite" in the paper's page, to see how to properly cite the paper