¿Algún algoritmo rápido para árboles de expansión mínima cuando las longitudes de los bordes están restringidas?

Question

Supongamos que tiene un gráfico dirigido con longitudes de borde enteras no negativas que están en el rango de 0 a U - 1, inclusive. ¿Cuál es el algoritmo más rápido para calcular un árbol de expansión mínimo de este gráfico? Todavía podemos usar algoritmos de árbol de expansión mínimo existentes, como el algoritmo O (m log n) de Kruskal) o el algoritmo de Prim (O (m + n log n)). Sin embargo, para los casos en que U es pequeño, creo que debería ser posible hacerlo mucho mejor.

¿Hay algún algoritmo que sea competitivo con los algoritmos MST más tradicionales que puedan explotar el hecho de que las longitudes de los bordes están restringidas para estar en algún rango?

Gracias!

Answer 1

Fredman-Willard dio un algoritmo O (m + n) para las longitudes de los extremos enteros en la RAM de costo unitario.

Podría decirse que no es una gran mejora: sin la restricción de longitudes de borde (es decir, las longitudes son un tipo de datos opacos que solo admiten comparaciones), Chazelle dio un algoritmo O (m alpha (m, n) + n) (alfa es la función inversa de Ackermann) y Karger-Klein-Tarjan dio un algoritmo O aleatorio (m + n).

No creo que la idea de Darren conduzca a un algoritmo O (m + n + U) -time. Jarnik ("Prim") no usa su cola de prioridad monótonamente, por lo que los segmentos pueden escanearse varias veces; Kruskal requiere una estructura de datos disjuntos, que no puede ser O (m + n).

Answer 2

Con pesas de borde entero puede usar el agrupamiento para lograr una cola de prioridad con el peor de los casos O(1) complejidad, pero O(U) complejidad de espacio adicional.

Dentro de los algoritmos MST que ha mencionado, debe poder reemplazar las colas de prioridad basadas en comparación con esta estructura entera y, por lo tanto, eliminar la dependencia O(log(n)) en los requisitos de complejidad. Espero que termines con una complejidad general en el estilo de O(n + m).

Esencialmente configuración de un conjunto de listas enlazadas comprimidos, en donde cada lista es indexado por el costo asociado con el cubo (entero!):

struct bucket_list 
{ 
    _cost; // array[0..N-1] holding current cost for each item 

    _head; // array[0..U-1] holding index of first item in each bucket 

    _next; // array[0..N-1] where _next[i] is the next item 
      // in a list for the ith item 

    _prev; // array[0..N-1] where _prev[i] is the last item 
      // in a list for the ith item 
}; 

Esta estructura se basa en el hecho de que cada elemento puede solo estar en una sola lista de cubos a la vez.

Basado en esta estructura se puede lograr peor de los casos O(1) complejidad de estas operaciones:

push(item, cost); // push an item onto the head of the appropriate bucket list 

_pop(item, cost); // _pop an item from (anywhere!) within a bucket list 

update(item, old_cost, new_cost); // move an item between buckets by combining 
            // push and _pop 

Para utilizar esta estructura como una cola de prioridad sólo tiene que mantener un índice que señala en el cubo mínimo actual para escanear. Cuando desee obtener el siguiente artículo de menor costo, simplemente extraiga el artículo principal de este segmento. Si la cubeta está vacía, aumenta el índice de la cubeta hasta que encuentre una que no esté vacía.

Por supuesto, si U se vuelve muy grande, la complejidad del espacio extra, y la posibilidad de una distribución escasa de los elementos sobre los cubos puede hacer este tipo de enfoque poco atractivo.