Le raffinement de partition est une technique dans laquelle vous commencez avec un ensemble fini d'objets et divisez progressivement l'ensemble. Certains problèmes, comme la minimisation DFA, peuvent être résolus en utilisant le raffinement de partition assez efficacement. Je ne connais pas d'autres problèmes qui sont généralement résolus en utilisant le raffinement des partitions autres que ceux répertoriés sur la page Wikipedia. Parmi tous ces problèmes, la page Wikipedia en mentionne deux pour lesquels des algorithmes basés sur le raffinement de partition s'exécutent en temps linéaire. Il y a le tri topologique lexicographiquement ordonné [1] et un algorithme de recherche lexicographique en largeur d'abord [2].
Y a-t-il d'autres exemples ou références à des problèmes qui peuvent être résolus en utilisant le raffinement de partition très efficacement, ce qui signifie quelque chose de mieux que log-linéaire en termes de temps?
[1] Sethi, Ravi, «Scheduling graphs on two processors», SIAM Journal on Computing 5 (1): 73–82, 1976.