Inne zastosowania wzmocnienia rozgałęzień Karger-Stein?

Właśnie nauczyłem losowego algorytmu skrótu Karger-Stein w mojej klasie algorytmów dla absolwentów. To prawdziwy klejnot algorytmiczny , więc nie mogę tego nie uczyć, ale zawsze denerwuje mnie, ponieważ nie znam innych zastosowań głównej techniki. (Trudno więc przypisać pracę domową, która doprowadzi ten punkt do domu.)

Algorytm Kargera i Steina jest udoskonaleniem wcześniejszego algorytmu Kargera, który iteracyjnie kurczy losowe krawędzie, dopóki wykres nie będzie miał tylko dwóch wierzchołków; ten prosty algorytm działa w czasie i zwraca minimalne cięcie z prawdopodobieństwem Ω ( 1 / n 2 ) , gdzie n jest liczbą wierzchołków na wykresie wejściowym. Udoskonalony „rekurencyjny algorytm skurczu” iteracyjnie kurczy losowe krawędzie, aż liczba wierzchołków spadnie z n do n / $O(n^2)$$\Omega(1/n^2)$$n$$n$ , rekurencyjnie wywołuje siędwukrotniena pozostałym wykresie i zwraca mniejsze z dwóch powstałych cięć. Prosta implementacja udoskonalonego algorytmu działa w czasieO(n2logn)i zwraca minimalne cięcie z prawdopodobieństwemΩ(1/logn). (Istnieją bardziej wydajne implementacje tych algorytmów i lepsze algorytmy losowe).$n/\sqrt{2}$$O(n^2\log n)$$\Omega(1/\log n)$

Jakie inne randomizowane algorytmy wykorzystują podobne techniki wzmocnienia rozgałęziania? Szczególnie interesują mnie przykłady, które (oczywiście) nie obejmują cięć graficznych.

@JeffE, tutaj jest papier, który liczy minimalne cykle wagowe na wykresie. O ile pamiętam, zdecydowanie był inspirowany techniką / wynikiem Kargera i był to zabawny dowód. Mam nadzieję, że to pomaga w nauczaniu.