LISTAS RELACIONADAS CON LOS MATEMÁTICAS - ALGORITMOS

problema del camino más largo es el problema de encontrar un camino simple de longitud máxima en un gráfico dado. Una ruta se llama simple si no tiene vértices repetidos; la longitud de una trayectoria puede medirse por su número de bordes, o (en gráficos ponderados ) por la suma de los pesos de sus bordes. En contraste con el problema de la ruta más corta , que puede resolverse en tiempo polinomial en gráficos sin ciclos de peso negativo, el problema de la ruta más larga es NP-hard y la versión de decisión del problema, que pregunta si existe una ruta de al menos alguna dada. longitud, es NP-completa. Esto significa que el problema de decisión no se puede resolver en tiempo polinomial para gráficos arbitrarios a menos que  P = NP . También se conocen resultados de dureza más fuertes que muestran que es difícil aproximarse . Sin embargo, tiene una solución de tiempo lineal para gráficos acíclicos dirigidos , que tiene aplicaciones importantes para encontrar la ruta crítica en los problemas de programación.

Dureza NP [ editar ]

La dureza NP del problema del camino más largo no ponderado se puede mostrar usando una reducción del problema del camino Hamiltoniano : un gráfico G tiene un camino Hamiltoniano si y solo si su camino más largo tiene la longitud n  - 1, donde n es el número de vértices en G . Debido a que el problema de la ruta hamiltoniana es NP-completo, esta reducción muestra que la versión de decisión del problema de la ruta más larga también es NP-completa. En este problema de decisión, la entrada es un gráfico G y un número k ; la salida deseada es "sí" si G contiene una ruta de k o más bordes, y no lo contrario. ^[1]

Si el problema de la ruta más larga podría resolverse en tiempo polinomial, podría usarse para resolver este problema de decisión, encontrando una ruta más larga y luego comparando su longitud con el número  k . Por lo tanto, el problema del camino más largo es NP-duro. La pregunta "¿existe una ruta simple en un gráfico dado con al menos k bordes" es NP-completa. ^[2]

En los gráficos completos ponderados con ponderaciones de borde no negativas, el problema de la ruta más larga ponderada es el mismo que el problema de la ruta del vendedor ambulante , porque la ruta más larga siempre incluye todos los vértices. ^[3]

Acíclicos gráficos y rutas críticas [ editar ]

Un camino más largo entre dos vértices dados s y t en un gráfico ponderado G es la misma cosa que un camino más corto en un gráfico - G derivado de G cambiando cada peso a su negación. Por lo tanto, si los caminos más cortos se pueden encontrar en - G , entonces los caminos más largos también pueden ser encontrados en G . ^[4]

Para la mayoría de los gráficos, esta transformación no es útil, ya que crea ciclos de longitud negativa en - G . Pero si G es un gráfico acíclico dirigido , entonces no se pueden crear ciclos negativos, y se puede encontrar una ruta más larga en G en tiempo lineal aplicando un algoritmo de tiempo lineal para las rutas más cortas en - G , que también es un gráfico acíclico dirigido. ^[4] Por ejemplo, para cada vértice v en un DAG dado, la longitud del camino más largo que termina en v se puede obtener mediante los siguientes pasos:

1. Encontrar un ordenamiento topológico del DAG dado.
2. Para cada vértice v del DAG, en el ordenamiento topológico, calcule la longitud del camino más largo que termina en v mirando sus vecinos entrantes y agregando uno a la longitud máxima registrada para esos vecinos. Si v no tiene vecinos entrantes, establezca la longitud de la ruta más larga que termina en v en cero. En cualquier caso, registre este número para que los pasos posteriores del algoritmo puedan acceder a él.

Una vez hecho esto, se puede obtener la ruta más larga en todo el DAG comenzando en el vértice v con el mayor valor registrado, luego retrocediendo repetidamente hacia su vecino entrante con el mayor valor registrado, e invirtiendo la secuencia de vértices que se encuentran en de esta manera.

El método de ruta crítica para programar un conjunto de actividades implica la construcción de un gráfico acíclico dirigido en el que los vértices representan hitos del proyecto y los bordes representan actividades que deben realizarse después de un hito y antes de otro; cada borde está ponderado por una estimación de la cantidad de tiempo que llevará completar la actividad correspondiente. En tal gráfico, la ruta más larga desde el primer hito hasta la última es la ruta crítica, que describe el tiempo total para completar el proyecto. ^[4]

Las rutas más largas de los gráficos acíclicos dirigidos también se pueden aplicar en un dibujo de capas : la asignación de cada vértice v de una gráfica acíclica dirigida G a la capa cuyo número es la longitud de la ruta más larga que termina en v da como resultado una asignación de capa para G con el mínimo posible número de capas. ^[5]

Aproximación [ editar ]

Björklund, Husfeldt y Khanna (2004) escriben que el problema del camino más largo en gráficos no direccionados no ponderados "es notorio por la dificultad de comprender su dureza de aproximación". ^[6] El mejor algoritmo de aproximación de tiempo polinomial conocido para este caso logra solo una relación de aproximación muy débil,$${\ displaystyle n / \ exp (\ Omega ({\ sqrt {\ log n}}))}. ^[7] Para todos{\ displaystyle \ epsilon> 0}, no es posible aproximar el camino más largo dentro de un factor de$${\ displaystyle 2 ^ {(\ log n) ^ {1- \ epsilon}}}a menos que NP esté contenido dentro del tiempo determinístico cuasi-polinomial ; sin embargo, existe una gran brecha entre este resultado de inoportabilidad y los algoritmos de aproximación conocidos para este problema. ^[8]

En el caso de gráficos no ponderados pero dirigidos, se conocen resultados de inoportabilidad sólidos. Para cada{\ displaystyle \ epsilon> 0} El problema no puede ser aproximado a un factor de $${\ displaystyle n ^ {1- \ epsilon}} a menos que P = NP, y con supuestos teóricos de complejidad más fuertes, no se pueda aproximar a un factor de $${\ displaystyle n / \ log ^ {2+ \ epsilon} n}. ^[6] La técnica de codificación por colores se puede utilizar para encontrar rutas de longitud logarítmica, si existen, pero esto da una relación de aproximación de solo$${\ displaystyle O (n / \ log n)}. ^[9]

Complejidad parametrizada [ editar ]

El problema de la ruta más larga es manejable por parámetros fijos cuando está parametrizado por la longitud de la ruta. Por ejemplo, se puede resolver en tiempo lineal en el tamaño del gráfico de entrada (pero exponencial en la longitud de la ruta), mediante un algoritmo que realiza los siguientes pasos:

1. Realice una búsqueda en profundidad de la gráfica. Dejar$${\ displaystyle d}ser la profundidad del árbol de búsqueda primero en profundidad resultante .
2. Utilice la secuencia de rutas de raíz a hoja del árbol de búsqueda en profundidad, en el orden en que fueron atravesadas por la búsqueda, para construir una descomposición de ruta del gráfico, con el ancho de ruta$${\ displaystyle d}.
3. Aplique programación dinámica a esta descomposición de ruta para encontrar la ruta más larga en el tiempo$${\ displaystyle O (d! 2 ^ {d} n)}, dónde $${\ displaystyle n} Es el número de vértices en la gráfica.

Dado que la ruta de salida tiene una longitud al menos tan grande como $${\ displaystyle d}, el tiempo de ejecución también está limitado por $${\ displaystyle O (\ ell! 2 ^ {\ ell} n)}, dónde $${\ displaystyle \ ell}es la longitud del camino más largo. ^[10] Usando el código de colores, la dependencia de la longitud del camino puede reducirse a exponencial simple. ^{[9] [11] [12] [13]} Una técnica de programación dinámica similar muestra que el problema de la ruta más larga también es manejable por parámetros fijos cuando está parametrizado por el ancho de árbol del gráfico.

Para gráficos de ancho de clique acotado , la ruta más larga también puede resolverse mediante un algoritmo de programación dinámica de tiempo polinomial. Sin embargo, el exponente del polinomio depende del ancho de clique de la gráfica, por lo que este algoritmo no es manejable por parámetros fijos. El problema de la ruta más larga, parametrizado por clique-width, es difícil para la clase de complejidad parametrizada$${\ displaystyle W [1]}, mostrando que es poco probable que exista un algoritmo manejable de parámetro fijo. ^[14]

Clases especiales de grafos [ editar ]

Dijkstra propuso un algoritmo de tiempo lineal para encontrar la ruta más larga en un árbol en la década de 1960, mientras que en 2002 se publicó una prueba formal de este algoritmo. ^[15] Además, la ruta más larga se puede calcular en tiempo polinomial en árboles ponderados, en gráficos de bloques, en cactus, ^[16] en gráficos de permutación bipartita, ^[17] y en gráficos ptolemaicos . ^[18]

Para la clase de gráficos de intervalo , un$${\ displaystyle O (n ^ {4})}Se conoce el algoritmo de tiempo, que utiliza un enfoque de programación dinámica. ^[19] Este enfoque de programación dinámica ha sido explotado para obtener algoritmos de tiempo polinomial en las clases mayores de gráficos de arco circular ^[20] y de gráficos de comparabilidad (es decir, de los complementos de gráficos de comparabilidad , que también contienen gráficos de permutación ), ^[21]ambos tienen el mismo tiempo de ejecución$${\ displaystyle O (n ^ {4})}. El último algoritmo se basa en las propiedades especiales del ordenamiento de vértices de la búsqueda por profundidad de lexicografía (LDFS) ^[22] de los gráficos de comparabilidad. Para los gráficos de comparabilidad también un algoritmo de tiempo polinomial alternativo con mayor tiempo de ejecución$${\ displaystyle O (n ^ {7})}es conocido, que se basa en el diagrama de Hasse del conjunto parcialmente ordenado definido por el complemento del gráfico de co-comparabilidad de entrada. ^[23]

Además, el problema del camino más largo se puede resolver en tiempo polinomial en cualquier clase de gráficos con ancho de árbol acotado o ancho de camarilla acotado, como los gráficos de distancia hereditaria . Finalmente, es claramente NP-duro en todas las clases de gráficos en las que el problema de la trayectoria de Hamilton es NP-duro, como en gráficos divididos , gráficos circulares y gráficos planares .

El algoritmo de Borůvka es un algoritmo codicioso para encontrar un árbol de expansión mínimo en un gráfico para el que todos los pesos de bordes son distintos, o un bosque de expansión mínimo en el caso de un gráfico que no está conectado.

Fue publicado por primera vez en 1926 por Otakar Borůvkacomo un método para construir una red eléctrica eficiente para Moravia . ^{[1] [2] [3]} El algoritmo fue redescubierto por Choquet en 1938; ^[4] nuevamente por Florek , Łukasiewicz , Perkal , Steinhaus y Zubrzycki en 1951; ^[5] y nuevamente por Georges Sollin en 1965. ^[6] Este algoritmo es frecuentemente llamado algoritmo de Sollin , especialmente en la literatura de computación paralela .

El algoritmo comienza por encontrar el borde de menor peso que incide en cada vértice del gráfico y agregar todos esos bordes al bosque. Luego, repite un proceso similar para encontrar el borde de peso mínimo de cada árbol construido hasta el momento en un árbol diferente, y agregar todos esos bordes al bosque. Cada repetición de este proceso reduce el número de árboles, dentro de cada componente conectado del gráfico, a la mitad de este valor anterior, por lo que, después de muchas repeticiones logarítmicas, el proceso finaliza. Cuando lo hace, el conjunto de bordes que ha agregado forma el bosque de expansión mínimo.

Animación del algoritmo de Boruvka.

Pseudocódigo [ editar ]

Designando cada vértice o conjunto de vértices conectados como " componente ", el pseudocódigo para el algoritmo de Borůvka es:

Entrada: una gráfica G cuyos bordes tienen pesos distintos
 Inicialice un bosque F para que sea un conjunto de árboles de un solo vértice, uno para cada vértice de la gráfica.
 Mientras que F tiene más de un componente:
   Encuentra los componentes conectados de F y etiqueta cada vértice de G por su componente
   Inicialice el borde más barato para cada componente a "Ninguno"
   Por cada borde uv de g :
     Si u y v tienen diferentes etiquetas de componentes:
       Si uv es más barato que el borde más barato para el componente de u :
         Establezca uv como el borde más barato para el componente de u 
       Si uv es más barato que el borde más barato para el componente de v :
         Establecer uv como el borde más barato para el componente de v
   Para cada componente cuyo borde más barato no sea "Ninguno":
     Añadir su borde más barata de F 
 Salida: F es el bosque de expansión mínimo de G .

Si los bordes no tienen pesos distintos, entonces se puede usar una regla consistente para romper el empate (por ejemplo, romper los lazos con los identificadores de objeto de los bordes). Una optimización (no necesaria para el análisis) es eliminar de G cada borde que se encuentre para conectar dos vértices en el mismo componente entre sí.

Complejidad [ editar ]

Se puede demostrar que el algoritmo de Borvka toma las iteraciones O (log V ) del bucle externo hasta que termina, y por lo tanto se ejecuta en el tiempo O ( E log V ), donde E es el número de bordes, y V es el número de vértices en G . En los gráficos planos , y más generalmente en las familias de gráficos cerrados en operaciones menores del gráfico , se puede hacer que se ejecute en tiempo lineal, eliminando todo menos el borde más barato entre cada par de componentes después de cada etapa del algoritmo. ^[7]

Ejemplo [ editar ]

Imagen	componentes	Descripción
	{A}  {B}  {C}  {D}  {E}  {F}  {G}	Este es nuestro gráfico ponderado original. Los números cerca de los bordes indican su peso. Inicialmente, cada vértice en sí mismo es un componente (círculos azules).
	{A, B, D, F}  {C, E, G}	En la primera iteración del bucle externo, se agrega el borde de peso mínimo de cada componente. Algunos bordes se seleccionan dos veces (AD, CE). Quedan dos componentes.
	{A, B, C, D, E, F, G}	En la segunda y última iteración, se agrega el borde de peso mínimo de cada uno de los dos componentes restantes. Estos pasan a ser el mismo borde. Queda un componente y estamos listos. El borde BD no se considera porque ambos puntos finales están en el mismo componente.

Otros algoritmos [ editar ]

Otros algoritmos para este problema incluyen el algoritmo de Prim y el algoritmo de Kruskal . Se pueden obtener algoritmos paralelos rápidos combinando el algoritmo de Prim con los de Borůvka. ^[8]

Un algoritmo de árbol de expansión mínimo aleatorio más rápido basado en parte en el algoritmo de Borůvka debido a Karger, Klein y Tarjan se ejecuta en el tiempo O ( E ) esperado . ^[9] El algoritmo de árbol de expansión mínimo más conocido (determinístico) de Bernard Chazelle también se basa en parte en el de Borůvka y se ejecuta en tiempo O ( E α ( E , V )) , donde α es la inversa de la función Ackermann . ^[10] Estos algoritmos aleatorios y deterministas combinan los pasos del algoritmo de Borůvka, reduciendo el número de componentes que quedan por conectar, con pasos de un tipo diferente que reducen el número de bordes entre pares de componentes.

El algoritmo de Kruskal es un algoritmo de árbol de expansión mínimo que encuentra un borde del menor peso posible que conecta dos árboles del bosque. ^[1] Es un algoritmo codicioso en la teoría de gráficos, ya que encuentra un árbol de expansión mínimo para un gráfico ponderado conectado que agrega arcos de costos crecientes en cada paso. ^[1] Esto significa que encuentra un subconjunto de los bordes que forma un árbol que incluye cada vértice , donde se minimiza el peso total de todos los bordes del árbol. Si el gráfico no está conectado, encuentra un bosque de expansión mínimo(un árbol de expansión mínimo para cada componente conectado ).

Este algoritmo apareció por primera vez en Proceedings of the American Mathematical Society , pp. 48–50 en 1956, y fue escrito por Joseph Kruskal . ^[2]

Otros algoritmos para este problema incluyen el algoritmo de Prim , Reverse-eliminar algoritmo y el algoritmo de Borůvka .

Algoritmo [ editar ]

• cree un bosque F (un conjunto de árboles), donde cada vértice en el gráfico es un árbol separado
• Crea un conjunto S que contenga todos los bordes del gráfico.
• mientras que S no es vacío y F aún no abarca
  • quitar un borde con un peso mínimo de S
  • Si el borde eliminado conecta dos árboles diferentes, entonces agréguelo al bosque F , combinando dos árboles en un solo árbol.

Al finalizar el algoritmo, el bosque forma un bosque de expansión mínima del gráfico. Si el gráfico está conectado, el bosque tiene un solo componente y forma un árbol de expansión mínimo

Pseudocódigo [ editar ]

Una demo para el algoritmo de Kruskal basado en la distancia euclidiana.

El siguiente código se implementa con una estructura de datos de conjuntos disjuntos :

KRUSKAL (G):
1 A = ∅
2 foreach v ∈ GV:
3 CONFIGURAR (v)
4 foreach (u, v) en GE ordenados por peso (u, v), aumentando:
5     si FIND-SET (u) ≠ FIND-SET (v):
6 A = A ∪ {(u, v)}
7 UNIÓN (ENCONTRAR CONJUNTO (u), ENCONTRAR CONJUNTO (v))
8 retorno A

Complejidad [ editar ]

Se puede mostrar que el algoritmo de Kruskal se ejecuta en tiempo O ( E log E ) o, de manera equivalente, tiempo O ( E log V ), donde E es el número de bordes en el gráfico y V es el número de vértices, todos con estructuras de datos simples . Estos tiempos son equivalentes porque:

• E es a lo sumo$${\ displaystyle V ^ {2}} y $${\ displaystyle \ log V ^ {2} = 2 \ log V} es $${\ displaystyle O (\ log V)}.
• Cada vértice aislado es un componente separado del bosque de expansión mínimo. Si ignoramos los vértices aislados obtenemos V ≤ 2 E , entonces el log V es$${\ displaystyle O (\ log E)}.

Podemos lograr este límite de la siguiente manera: primero ordene los bordes por peso utilizando un orden de comparación en tiempo O ( E log E ); esto permite que el paso "quitar un borde con el peso mínimo de S " funcione a tiempo constante. A continuación, utilizamos una estructura de datos de conjunto disjunto para realizar un seguimiento de qué vértices están en qué componentes. Necesitamos realizar operaciones O ( V ), ya que en cada iteración conectamos un vértice al árbol de expansión, dos operaciones de "búsqueda" y posiblemente una unión para cada borde. Incluso una simple estructura de datos de conjuntos disjuntos, tales como bosques de conjuntos disjuntos con unión por rango puede realizar operaciones O ( V ) en O ( Vlog V ) tiempo. Por lo tanto, el tiempo total es O ( E log E ) = O ( E log V ).

Siempre que los bordes ya estén ordenados o puedan ordenarse en tiempo lineal (por ejemplo, con clasificación por conteo o clasificación por radios ), el algoritmo puede usar una estructura de datos de conjuntos separadosmás sofisticada para ejecutarse en tiempo O ( E α ( V )) , donde α es el inverso de la función Ackermann de un solo valor que crece de manera extremadamente lenta .

Ejemplo [ editar ]

Imagen	Descripción
	AD y CE son los bordes más cortos, con una longitud de 5, y AD se haelegido arbitrariamente , por lo que está resaltado.
	CE es ahora el borde más corto que no forma un ciclo, con una longitud de 5, por lo que se resalta como el segundo borde.
	El siguiente borde, DF con longitud 6, se resalta usando casi el mismo método.
	Los siguientes bordes más cortos son AB y BE , ambos con longitud 7. ABse elige arbitrariamente y se resalta. El borde BD se ha resaltado en rojo, porque ya existe una ruta (en verde) entre B y D , por lo que formaría un ciclo ( ABD ) si se eligiera.
	El proceso continúa resaltando el siguiente borde más pequeño, BE con longitud 7. Muchos más bordes se resaltan en rojo en esta etapa: AC porque formaría el bucle BCE , DE porque formaría el bucle DEBA y FE porque lo haría formulario FEBAD .
	Finalmente, el proceso finaliza con el borde EG de longitud 9 y se encuentra el árbol de expansión mínimo.

Prueba de corrección [ editar ]

La prueba consta de dos partes. Primero, se demuestra que el algoritmo produce un árbol de expansión . En segundo lugar, se demuestra que el árbol de expansión construido tiene un peso mínimo.

Árbol de expansión [ editar ]

Dejar $${\ displaystyle G} Ser un gráfico conectado, ponderado y dejar $${\ displaystyle Y} ser el subgrafo de $${\ displaystyle G} Producido por el algoritmo. $${\ displaystyle Y} no puede tener un ciclo, estar dentro de un subárbol y no entre dos árboles diferentes. $${\ displaystyle Y} no se puede desconectar, ya que el primer borde encontrado que une dos componentes de $${\ displaystyle Y}Habría sido añadido por el algoritmo. Así,$${\ displaystyle Y}es un árbol de expansión $${\ displaystyle G}.

Minimalidad [ editar ]

Se demuestra que la siguiente proposición P es cierto por inducción : Si F es el conjunto de aristas elegidas en cualquier etapa del algoritmo, entonces hay algún árbol de expansión mínimo que contiene F .

• Claramente, P es verdadero al principio, cuando F está vacío: cualquier árbol de expansión mínimo funcionará, y existe uno porque un gráfico conectado ponderado siempre tiene un árbol de expansión mínimo.
• Supongamos ahora P es cierto para algunos borde conjunto no final F y dejar que T sea un árbol de expansión mínimo que contiene F .
  • Si el siguiente borde elegido e también está en T , entonces P es verdadero para F + e .
  • De lo contrario, e no es en T , y T + e tiene un ciclo C . Este ciclo contiene bordes que no pertenecen a F , ya que e no forma un ciclo en C , pero lo hace en T . Sea f una ventaja en C pero no en F$${\ displaystyle \ cup \ {e \}}. Tenga en cuenta que f pertenece también a T , y que P no ha sido considerado por el algoritmo, y por lo tanto un peso al menos tan grande como e . Entonces T - f + e es un árbol, y tiene el mismo peso o menos como T. Así que T - f + e es un árbol de expansión mínimo que contiene F + e y nuevamente P se mantiene.
• Por lo tanto, según el principio de inducción, P se mantiene cuando F se ha convertido en un árbol de expansión, lo que solo es posible si F es un árbol de expansión mínimo en sí mismo.

Algoritmo paralelo [ editar ]

El algoritmo de Kruskal es inherentemente secuencial y difícil de paralelizar. Sin embargo, es posible realizar la clasificación inicial de los bordes en paralelo o, alternativamente, usar una implementación paralela de un montón binario para extraer el borde de peso mínimo en cada iteración ^[3] . Como la clasificación paralela es posible en el tiempo.$${\ displaystyle O (n)} en $${\ displaystyle O (\ log n)}En los procesadores ^[4] , el tiempo de ejecución del algoritmo de Kruskal se puede reducir a O ( E α ( V )), donde α nuevamente es la inversa de la función Ackermann de un solo valor .

Una variante del algoritmo de Kruskal, llamada Filter-Kruskal, ha sido descrita por Osipov et al. ^[5] y es más adecuado para la paralelización. La idea básica detrás de Filter-Kruskal es dividir los bordes de forma similar a ordenar rápidamente y filtrar los bordes que conectan los vértices del mismo árbol para reducir el costo de la clasificación. El siguiente Pseudocódigo demuestra esto.

FILTRO-KRUSKAL (G):
1 si | GE | 
2     vuelta KRUSKAL (G)
3 pivotes = ELEGIR-ALEATORIO (GE)
4 {\ displaystyle E _ {<=}}
  
, {\ displaystyle E _ {>}}
  
 = PARTICION (GE, pivote)
5 A = FILTRO-KRUSKAL ({\ displaystyle E _ {<=}}
  
)
6 {\ displaystyle E _ {>}}
  
 = FILTRO ({\ displaystyle E _ {>}}
  
)
7 A = A ∪ FILTRO-KRUSKAL ({\ displaystyle E _ {>}}
  
)
8 retorno A

PARTICIÓN (E, pivote):
1 {\ displaystyle E _ {<=}}
  
 = ∅, {\ displaystyle E _ {>}}
  
 = ∅
2 foreach (u, v) en E:
3     si el peso (u, v) <= pivote:
4       {\ displaystyle E _ {<=}}
  
 = {\ displaystyle E _ {<=}}
  
 ∪ {(u, v)}
5     sino 
6       {\ displaystyle E _ {>}}
  
 = {\ displaystyle E _ {>}}
  
 ∪ {(u, v)}
5 de vuelta {\ displaystyle E _ {<=}}
  
, {\ displaystyle E _ {>}}
  


FILTRO (E):
1 $${\ displaystyle E_ {filter}}
  
 = ∅
2 foreach (u, v) en E:
3     si FIND-SET (u) ≠ FIND-SET (v):
4       $${\ displaystyle E_ {filter}}
  
 = $${\ displaystyle E_ {filter}}
  
 ∪ {(u, v)}
5 de vuelta $${\ displaystyle E_ {filter}}
  

Filter-Kruskal se presta mejor para la paralelización, ya que la clasificación, el filtrado y la partición se pueden realizar fácilmente en paralelo al distribuir los bordes entre los procesadores ^[5] .

Finalmente, se han explorado otras variantes de una implementación paralela del algoritmo de Kruskal. Los ejemplos incluyen un esquema que usa hilos auxiliares para eliminar bordes que definitivamente no forman parte de la MST en segundo plano ^[6] , y una variante que ejecuta el algoritmo secuencial en p subgrafos, luego combina esas subgrafos hasta que solo una, la MST final, queda ^[7] .