Árvore de extensão mínima: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
cat |
|||
Linha 8:
O mais rápido algoritmo de árvore mínima de extensão foi desenvolvido por [[Bernard Chazelle]], e foi baseado no algoritmo de Borůvka's. Ele roda em um tempo de ''[[notação O |O]]''(''m'' α(''m'',''n'')), onde ''m'' é o número de arestas, ''n'' refere-se ao numero de vértices e α é a clássica função inversa da [[função de Ackermann]]. A função α cresce de forma extremamente lenta, então para todos os propósitos práticos ele pode ser considerado uma constante não maior que quatro; portanto o algoritmo de Chazelle chega muito perto de um tempo ''O''(''m'').
Qual é o algoritmo mais rápido possível para este problema? Isto é um dos mais antigos problemas em aberto na ciência da computação. Há claramente um limite linear inferior, já que é necessário examinar
=={{links}}==
* [http://danielamaral.wikidot.com/paa-2007-1-projeto-1-arvore-geradora-minima Comparação de algoritmos para o problema da árvore de extensão mínima] - Explicação detalhada de cinco algoritmos diferentes para o problema da árvore de extensão mínima, código completo de cada um deles e comparação de performance entre eles.
[[Categoria:Teoria dos grafos]]
| |||