Abordagem de refinamento iterativo para o problema da árvore geradora com número mínimo de vértices Branch

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

02/03/2011

RESUMO

O Problema da Árvore Geradora com Número Mínimo de Vértices Branch (do inglês, Minimum Branch Vertices Problem ou MBV) consiste em, dado um grafo G=(V,E) conexo, não direcionado e não valorado, encontrar a árvore geradora T dentre todas as árvores geradoras de G que possui a menor quantidade de vértices com grau maior ou igual à 3, denominados vértices branch. Tal problema surge na tomada de decisão sobre onde alocar switches WDM especiais no projeto de redes ópticas multicast, e foi provado ser da classe NP-Completo. Neste trabalho o problema é investigado por meio de uma proposta de heurística que baseia-se na abordagem de Refinamento Iterativo (IR), onde uma árvore geradora irrestrita é modificada usando o artifício de substituição de arcos considerados infratores em T por arcos de G de forma que a sua topologia original seja ajustada para possuir a menor quantidade de vértices branch possível. Experimentos foram realizados sobre 6 diferentes conjuntos de instâncias, comparando-se os resultados pelo algoritmo IR proposto com os resultados de duas outras heurísticas existentes para o problema. A análise dos resultados experimentais sugere que o algoritmo IR pode encontrar soluções de melhor qualidade do que estas heurísticas conforme a densidade de G aumenta.

ASSUNTO(S)

computação teses. teoria dos grafos teses. programação heurística ses

ACESSO AO ARTIGO

Documentos Relacionados