Loading...
Please wait, while we are loading the content...
Similar Documents
Abordagem de refinamento iterativo para o problema da árvore geradora com número mínimo de vértices Branch
| Content Provider | Semantic Scholar |
|---|---|
| Author | Silva, D. M. |
| Copyright Year | 2011 |
| Abstract | O Problema da Arvore Geradora com Numero Minimo de Vertices Branch (do ingles, Minimum Branch Vertices Problem ou MBV) consiste em, dado um grafo G=(V,E) conexo, nao direcionado e nao valorado, encontrar a arvore geradora T dentre todas as arvores geradoras de G que possui a menor quantidade de vertices com grau maior ou igual a 3, denominados vertices branch. Tal problema surge na tomada de decisao sobre onde alocar switches WDM especiais no projeto de redes opticas multicast, e foi provado ser da classe NP-Completo. Neste trabalho o problema e investigado por meio de uma proposta de heuristica que baseia-se na abordagem de Refinamento Iterativo (IR), onde uma arvore geradora irrestrita e modificada usando o artificio de substituicao de arcos considerados infratores em T por arcos de Gde forma que a sua topologia original seja ajustada para possuir a menor quantidade de vertices branch possivel. Experimentos foram realizados sobre 6 diferentes conjuntos de instâncias, comparando-se os resultados pelo algoritmo IR proposto com os resultados de duas outras heuristicas existentes para o problema. A analise dos resultadosexperimentais sugere que o algoritmo IR pode encontrar solucoes de melhor qualidade do que estas heuristicas conforme a densidade de G aumenta. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://repositorio.ufmg.br/bitstream/1843/SLSS-8GQJHW/1/diegomellosilva.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
