Variaciones del algoritmo de kruskal

El mínimo de filtro-Kruskal Algoritmo de árbol de expansión *
Osipov Vitaly, Peter Sanders, y † Johannes Singler
Resumen
Presentamos Filtro-Kruskal - una simple modificación de
algoritmo de Kruskal, que evita la clasificación que tiene bordes
"Obviamente" no en el MST. Para gráficas arbitrarias
con pesos al azar borde del filtro de Kruskal-se ejecuta en tiempo
O registro de m + n log n mn?, es decir, en tiempo lineal para no demasiado
grafos dispersos. Los experimentos indican que el algoritmo
tiene un rendimiento práctico muy bueno para todo el período
rango de densidades de borde. Un paralleliza igualmente simple-
ción parece ser el mejor algoritmo de la actualidad prácticas
en las máquinas multi-núcleo.
1 Introducción
Un árbol de expansión mínima (MST) de un grafo G =(V, E)
Es un subconjunto mínimo de peso total de E que se forma un lapso de-
ning árbol de la G. El problema MST ha sido intensamente
Estudió en el pasado, ya que es una red fundamental
problema de diseño con muchas aplicaciones y porque
permite al polinomio de tiempo elegante y multifacético-
algoritmos. En la práctica (en las máquinas secuenciales y en
memoria interna), dos algoritmossencillos que data
al menos la mitad de un siglo todavía mejores resultados en la mayoría de los casos
[17, 11, 6].
El algoritmo de Prim-Jarn'ık [8, 20] crece un árbol
a partir de un nodo arbitrario. Implementado con efi-
colas de prioridad suficiente, su tiempo de ejecución es O (m + n log n).
Incluso con colas de prioridad más simple, funciona bien para
borde azar weights1 - tiempo O m + nlog n log m
n? [18].
algoritmo de Kruskal [14] crece un bosque en el tiempo
O ((m + n) logm) mediante la exploración de los bordes con el fin de
aumento de peso y añadiendo los que se unen dos árboles
en el bosque actual. En la práctica, Kruskal outperfoms
Jarn'ık-Prim para grafos dispersos. Para gráficos más denso,
Kruskal sufre de la junta (mlogm) tiempo necesario para
clasificación detodos los bordes. Por lo tanto, es una idea natural
evitar la clasificación de los bordes pesados que no pueden contribuir a la
MST. Kershenbaum y van Slyke [12, 17] Para ello,
la construcción de una cola de prioridad de los bordes en el tiempo lineal. A continuación,
? Parcialmente apoyado por la beca DFG SA 933/3-1.
† ¨ Universit de Karlsruhe (TH), Alemania,
{Osipov, lijadoras, Singler} @ira.uka.de.
1here y en el siguiente se utiliza el siguiente modelo de
pesos al azar borde: borde de los pesos son diferentes, puede
de otro modo tienen valores arbitrarios, y se permutan al azar.
algoritmo de Kruskal posteriormente elimina el más ligero
borde hasta n - 1 aristas del árbol se han encontrado. Por
grafos aleatorios con pesos borde al azar, el MST
más ligero bordes se espera quesean entre los O (n log n)
bordes. Por lo tanto, tenemos un tiempo de ejecución promedio de
O m + n log2 n?. Por desgracia, la idea de no parar
ya si el MST contiene una gran ventaja única. Nota
que esto puede ocurrir incluso para los pesos borde al azar:
Considere la posibilidad de un "gráfico de paleta", que consiste de un azar
gráfico y una vía adicional de longitud k unido a un
de susnodos. El MST necesidades de todos los bordes de camino, sobre
mitad de los cuales pertenecen a la parte más pesada de los bordes
para los pesos borde azar. Brennan [4, 19] aplica
la idea de dejar de caché más eficiente mediante la integración de
algoritmo de Kruskal con quicksort (qKruskal). Aplicar
Kruskal a las entradas pequeñas. De lo contrario, como en el quicksort,
partición de losbordes en una parte de luz y una parte pesada.
Recurse en la parte de luz. Si el MST no está completa
sin embargo, recurse en la parte pesada.
Una idea clave de las mejoras más robusta de Kruskal
es filtrado - descartando a principios de los bordes que conectan los nodos
en el mismo componente de la forestal definida por el MST
bordes ya que se encuentran. En [12] de filtrado se aplica a los...