MO417 - Questão para a prova oral
Número: 070
Enunciado:
Sabemos que encontrar o caminho de custo mínimo em um grafo é um problema fácil de se resolver, porém encontrar o caminho de custo
máximo é um problema difícil. O que podemos afirmar sobre árvores geradoras de custo máximo?
- Não se conhecem algoritmos para encontrá-las em tempo polinomial
- Podem ser encontradas com pequenas modificações nos algoritmos
para árvores geradoras mínimas, mantendo a complexidade
- Os algoritmos mais eficientes para este problema são
bastante diferentes dos de árvore geradora mínima
- Os algoritmos conhecidos que encontram árvores geradoras
de custo máximo são polinomiais apenas para grafos esparsos.
- NDA
Autor(a): Pedro Henrique Del Bianco Hokama