Problemy, dla których algorytmy oparte na zawężaniu partycji działają szybciej niż w czasie logarytmicznym

Udoskonalenie partycji to technika, w której zaczynasz od skończonego zestawu obiektów i stopniowo dzielisz zestaw. Niektóre problemy, takie jak minimalizacja DFA, można rozwiązać dość skutecznie za pomocą zawężania partycji. Nie znam żadnych innych problemów, które zwykle rozwiązuje się za pomocą udoskonalenia partycji innych niż te wymienione na stronie Wikipedii. Spośród wszystkich tych problemów strona Wikipedii wymienia dwa, dla których algorytmy oparte na zawężaniu partycji działają w czasie liniowym. Istnieje uporządkowany leksykograficznie sortowanie topologiczne [1] i algorytm dla leksykograficznego przeszukiwania szerokości od pierwszego [2].

Czy są jakieś inne przykłady lub odniesienia do problemów, które można rozwiązać bardzo skutecznie za pomocą zawężania partycji, co oznacza coś lepszego niż loglinearnie pod względem czasu?

[1] Sethi, Ravi, „Planowanie wykresów na dwóch procesorach”, SIAM Journal on Computing 5 (1): 73–82, 1976.

[2] Rose, DJ, Tarjan, RE, Lueker, GS, „Algorytmiczne aspekty eliminacji wierzchołków na wykresach”, SIAM Journal on Computing 5 (2): 266–283, 1976.

Niektóre algorytmy rozkładu liniowego w czasie wykorzystują (pewien rodzaj) doprecyzowanie podziału, patrz np. Te algorytmy dla grafów skierowanych i niekierowanych .