Identifying elements of solutions of combinatorial optimization problems using measures of graph centrality

Este trabalho visa dar evidências de que medidas de centralidade em grafos podem
ser utilizadas para identificar elementos pertencentes a soluções de problemas de otimização combinatória de determinada categoria, mais especificamente aqueles que podem ser modelados por grafos. Para tanto, foram utilizadas cinco medidas de centralidade e o problema de minimização de vértices d-branch. Utilizando-se métricas comumente adotadas na área de Ciência de Dados para avaliar a acurácia de modelos preditivos multirrótulo, foi possı́vel verificar uma alta capacidade das medidas de centralidades em corretamente identificar vértices d-branch para um grande conjunto de instâncias do problema de minimização de vértices d-branch.