UTILIZANDO CENTRALIDADES DE GRAFOS E UM ALGORITMO ITERATED LOCAL SEARCH PARA RESOLVER O PROBLEMA DA ÁRVORE GERADORA COM NÚMERO MÍNIMO DE VÉRTICES D-BRANCH

Vol 56, 2024 - 309890
Trabalho completo (Oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

   Dado um grafo G conexo, não direcionado e não valorado, o problema da Árvore Geradora com Número Mínimo de Vértices d-branch (d-MBV) consiste em encontrar uma árvore geradora que possua a menor quantidade de vértices com grau estritamente maior que d, para d ≥ 2. A aplicação direta desse problema é, por exemplo, na alocação de switches em projetos de redes óticas. Centralidades de grafos são medidas que permitem determinar a importância de um vértice em um grafo, de acordo com diferentes critérios. Neste trabalho, mostra-se que algumas medidas de centralidade podem identificar vértices que devem pertencer a uma solução do problema d-MBV. Investigou-se o uso destas centralidades em uma heurística ILS desenvolvida para o problema d-MBV de modo a mostrar como o uso de diferentes centralidades influencia a capacidade da heurística em encontrar soluções de boa qualidade.

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!

Instituições
  • 1 UFRJ
  • 2 UFF
  • 3 Federal University of Espírito Santo
Eixo Temático
  • 14. OC – Otimização Combinatória
Palavras-chave
Problema d-MBV
Otimização Combinatória
Meta-heurísticas
Grafos
Mineração de Dados