¿Otras aplicaciones de la amplificación de ramificación Karger-Stein?

Acabo de enseñar el algoritmo de mincut aleatorio Karger-Stein en mi clase de algoritmos de posgrado. Esta es una verdadera joya algorítmica , así que no puedo no enseñarlo, pero siempre me deja frustrado, porque no conozco ninguna otra aplicación de la técnica principal. (Por lo tanto, es difícil asignar tareas que lleven el punto a casa).

El algoritmo de Karger y Stein es un refinamiento de un algoritmo anterior de Karger, que contrae de forma iterativa aristas aleatorias hasta que el gráfico solo tiene dos vértices; Este algoritmo simple se ejecuta en tiempo y devuelve un corte mínimo con probabilidad Ω ( 1 / n 2 ) , donde n es el número de vértices en el gráfico de entrada. El refinado "Algoritmo de contracción recursiva" contrata iterativamente aristas aleatorias hasta que el número de vértices cae de n a n / $O(n^2)$$\Omega(1/n^2)$$n$$n$ , recursivamente se llama a sí mismodos vecesen el gráfico restante, y devuelve el menor de los dos cortes resultantes. Una implementación sencilla del algoritmo refinado se ejecuta en tiempoO(n2logn)y devuelve un corte mínimo con probabilidadΩ(1/logn). (Hay implementaciones más eficientes de estos algoritmos y mejores algoritmos aleatorios).$n/\sqrt{2}$$O(n^2\log n)$$\Omega(1/\log n)$

¿Qué otros algoritmos aleatorios usan técnicas de amplificación de ramificación similares? Estoy especialmente interesado en ejemplos que no (obviamente) implican recortes de gráficos.

@JeffE, Aquí hay un artículo que cuenta los ciclos de peso mínimo en un gráfico. Hasta donde recuerdo, definitivamente fue inspirado por la técnica / resultado de Karger y fue una prueba divertida. Espero que esto ayude con la enseñanza.