Problèmes pour lesquels les algorithmes basés sur le raffinement de partition s'exécutent plus rapidement qu'en temps log-linéaire

20

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.

[2] Rose, DJ, Tarjan, RE, Lueker, GS, "Aspects algorithmiques de l'élimination des sommets sur les graphiques", SIAM Journal on Computing 5 (2): 266–283, 1976.

Juho
la source

Réponses:

2

Quelque temps linéaire des algorithmes de décomposition modulaire utilisation ( un certain type de) raffinement de partition, voir par exemple ces algorithmes pour dirigés et graphes non orientés .

frafl
la source
1
Pouvez-vous élaborer un peu plus sur la façon dont le raffinement de partition est utilisé dans ces cas? Sinon, ça a l'air intéressant!
Juho