Autres applications de l'amplification de branchement de Karger-Stein?

Je viens d'enseigner l' algorithme de raccourci aléatoire de Karger-Stein dans ma classe d'algorithmes diplômés. C'est un vrai bijou algorithmique , donc je ne peux pas ne pas l' enseigner, mais cela me laisse toujours frustré, car je ne connais pas d'autres applications de la technique principale. (Il est donc difficile d'attribuer des devoirs qui poussent le point à la maison.)

L'algorithme de Karger et Stein est un raffinement d'un algorithme antérieur de Karger, qui contracte de manière itérative des bords aléatoires jusqu'à ce que le graphe n'ait que deux sommets; cet algorithme simple s'exécute en temps et renvoie une coupure minimale avec une probabilité Ω ( 1 / n 2 ) , où n est le nombre de sommets dans le graphe d'entrée. L'algorithme raffiné de contraction récursive contracte de manière itérative des bords aléatoires jusqu'à ce que le nombre de sommets passe de n à n / $O(n^2)$$\Omega(1/n^2)$$n$$n$ , s'appelle récursivementdeux foissur le graphique restant et renvoie la plus petite des deux coupes résultantes. Une implémentation simple de l'algorithme raffiné s'exécute en tempsO(n2logn)et renvoie une coupure minimale avec une probabilitéΩ(1/logn). (Il existe des implémentations plus efficaces de ces algorithmes et de meilleurs algorithmes randomisés.)$n/\sqrt{2}$$O(n^2\log n)$$\Omega(1/\log n)$

Quels autres algorithmes randomisés utilisent des techniques d'amplification de branchement similaires? Je suis particulièrement intéressé par les exemples qui n'impliquent pas (évidemment) des coupes de graphe.

@JeffE, voici un article qui compte les cycles de poids minimum dans un graphique. Pour autant que je m'en souvienne, c'était définitivement inspiré par la technique / résultat de Karger et c'était une preuve amusante. J'espère que cela aide à l'enseignement.