Aplicación de Ordenamiento en Línea: Construcción Eficiente del Árbol Cobertor Mínimo
Rodrigo Paredes
An on-line sorting application is presented:
the optimization of Kruskal's algorithm for
Minimum Spanning Tree construction of a given graph G(V,E).
This optimization allows one to reduce Kruskal's algorithm
temporal complexity from O(|E| log|E|) to an
empirical time cost of the form C1 |E| + C2 k logk,
where k is the size of the edge subset of G that is
reviewed during the minimum spanning tree construction.
In practice, k is much less than |E|, and in the case of
complete graphs, this optimization has better performance than
Prim's algorithm.
Se presenta una aplicación de ordenamiento en línea:
la optimización del algoritmo de Kruskal para construir el
Árbol Cobertor Mínimo de un grafo G(V,E) dado.
Esta optimización permite reducir la complejidad temporal
del algoritmo de Kruskal de O(|E| log|E|) a un costo empírico
de tiempo de la forma C1 |E| + C2 k logk
donde k es el tamaño del subconjunto de aristas de G que
se revisan al construir el árbol cobertor mínimo.
En la práctica k es mucho menor que |E|, y en el caso
de grafos completos, esta optimización tiene mejor desempeño que
el algoritmo de Prim.