Masalah yang algoritma yang didasarkan pada perbaikan partisi berjalan lebih cepat daripada dalam waktu loglinear

Penyempurnaan partisi adalah teknik di mana Anda mulai dengan satu set terbatas objek dan semakin membelah set. Beberapa masalah, seperti minimisasi DFA, dapat diselesaikan dengan menggunakan penyempurnaan partisi dengan cukup efisien. Saya tidak tahu ada masalah lain yang biasanya diselesaikan dengan menggunakan perbaikan partisi selain yang terdaftar di halaman Wikipedia. Dari semua masalah ini, halaman Wikipedia menyebutkan dua algoritma yang berdasarkan perbaikan partisi berjalan dalam waktu linier. Ada jenis topologi yang diurutkan secara leksikografis [1] dan suatu algoritma untuk pencarian pertama-leksikografis [2].

Apakah ada contoh lain atau referensi untuk masalah yang dapat diselesaikan dengan menggunakan penyempurnaan partisi dengan sangat efisien, yang berarti sesuatu yang lebih baik daripada loglinear dalam hal waktu?

[1] Sethi, Ravi, "Penjadwalan grafik pada dua prosesor", Jurnal SIAM tentang Komputasi 5 (1): 73–82, 1976.

[2] Rose, DJ, Tarjan, RE, Lueker, GS, "Aspek algoritma penghapusan verteks pada grafik", Jurnal SIAM tentang Komputasi 5 (2): 266–283, 1976.

Beberapa algoritma dekomposisi modular waktu linier menggunakan (beberapa jenis) penyempurnaan partisi, lihat misalnya algoritma ini untuk grafik langsung dan tidak terarah .