MO417 - Questão para a prova oral

Número: 2010-070

Enunciado: Sabemos que encontrar caminhos de custo mínimo entre dois vértices num grafo é um problema fácil de se resolver. Porém, encontrar caminhos de custo máximo entre dois vértices é um problema difícil. O que podemos afirmar sobre árvores geradoras de custo máximo?

1. Não se conhecem algoritmos para encontrá-las em tempo polinomial
2. Podem ser encontradas com pequenas modificações nos algoritmos para árvores geradoras mínimas, mantendo a complexidade
3. Os algoritmos mais eficientes para este problema são bastante diferentes dos de árvore geradora mínima
4. Os algoritmos conhecidos que encontram árvores geradoras de custo máximo são polinomiais apenas para grafos esparsos.
5. NDA

Ideia original de: Pedro Henrique Del Bianco Hokama