Aplikasi lain dari amplifikasi percabangan Karger-Stein?

Saya baru saja mengajarkan algoritma mincut acak Karger-Stein di kelas algoritma lulusan saya. Ini adalah permata algoritmik yang nyata , jadi saya tidak bisa mengajarinya, tetapi selalu membuat saya frustrasi, karena saya tidak tahu aplikasi lain dari teknik utama. (Jadi sulit untuk menetapkan pekerjaan rumah yang mengarahkan poin ke rumah.)

Algoritma Karger dan Stein adalah penyempurnaan dari algoritma Karger sebelumnya, yang secara konteratif mengecilkan tepi acak hingga grafik hanya memiliki dua simpul; algoritma sederhana ini berjalan dalam waktu dan mengembalikan potongan minimum dengan probabilitas Ω ( 1 / n 2 ) , di mana n adalah jumlah simpul dalam grafik input. Algoritma Kontraksi Rekursif yang disempurnakan secara iteratif mengontrak tepi acak hingga jumlah simpul turun dari n ke n / $O(n^2)$$\Omega(1/n^2)$$n$$n$ , secara berulang menyebut dirinyadua kalipada grafik yang tersisa, dan mengembalikan potongan yang lebih kecil dari dua yang dihasilkan. Implementasi sederhana dari algoritma yang disempurnakan berjalan dalam waktuO(n2logn)dan mengembalikan potongan minimum dengan probabilitasΩ(1/logn). (Ada implementasi yang lebih efisien dari algoritma ini, dan algoritma acak yang lebih baik.)$n/\sqrt{2}$$O(n^2\log n)$$\Omega(1/\log n)$

Apa algoritma acak lain yang menggunakan teknik amplifikasi percabangan yang serupa? Saya terutama tertarik pada contoh yang tidak (jelas) melibatkan pemotongan grafik.

@ Jeff, Berikut adalah kertas yang menghitung siklus berat minimum dalam grafik. Sejauh yang saya ingat, itu pasti terinspirasi oleh teknik / hasil Krier dan itu adalah bukti yang menyenangkan. Semoga ini bisa membantu dalam pengajaran.