Andere Anwendungen der Karger-Stein-Verzweigungsverstärkung?

Ich habe gerade den Karger-Stein Randomized Mincut-Algorithmus in meiner Abschlussklasse unterrichtet. Dies ist ein echtes Juwel in Sachen Algorithmus , daher kann ich es nicht lehren, aber es macht mich immer frustriert, weil ich keine anderen Anwendungen der Haupttechnik kenne. (Daher ist es schwierig, Hausaufgaben zuzuweisen, die den Punkt nach Hause bringen.)

Der Algorithmus von Karger und Stein ist eine Weiterentwicklung eines früheren Algorithmus von Karger, bei dem zufällige Kanten iterativ kontrahiert werden, bis der Graph nur noch zwei Eckpunkte hat. Dieser einfache Algorithmus läuft in der Zeit und gibt einen minimalen Schnitt mit der Wahrscheinlichkeit Ω ( 1 / n 2 ) zurück , wobei n die Anzahl der Eckpunkte im Eingabegraphen ist. Der verfeinerte "Rekursive Kontraktionsalgorithmus" zieht iterativ zufällige Kanten zusammen, bis die Anzahl der Scheitelpunkte von n auf n / √ abfällt$O(n^2)$$\Omega(1/n^2)$$n$$n$ , ruft sichim verbleibenden Diagrammzweimalrekursivauf und gibt den kleineren der beiden resultierenden Schnitte zurück. Eine einfache Implementierung des verfeinerten Algorithmus läuft in der ZeitO(n2logn)und gibt einen minimalen Schnitt mit der WahrscheinlichkeitΩ(1/logn) zurück. (Es gibt effizientere Implementierungen dieser Algorithmen und besser randomisierte Algorithmen.)$n/\sqrt{2}$$O(n^2\log n)$$\Omega(1/\log n)$

Welche anderen randomisierten Algorithmen verwenden ähnliche Verzweigungsverstärkungstechniken? Ich interessiere mich besonders für Beispiele, die (offensichtlich) keine Grafikschnitte beinhalten.

@ JeffE, hier ist ein Artikel, der die minimalen Gewichtszyklen in einem Diagramm zählt. Soweit ich mich erinnere, war es definitiv inspiriert von Kargers Technik / Ergebnis und es war ein lustiger Beweis. Hoffe das hilft beim lehren.