Problemas para los cuales los algoritmos basados ​​en el refinamiento de la partición se ejecutan más rápido que en el tiempo loglineal

20

El refinamiento de partición es una técnica en la que comienza con un conjunto finito de objetos y divide progresivamente el conjunto. Algunos problemas, como la minimización de DFA, se pueden resolver utilizando el refinamiento de partición de manera bastante eficiente. No conozco otros problemas que generalmente se resuelven utilizando el refinamiento de la partición que no sean los enumerados en la página de Wikipedia. De todos estos problemas, la página de Wikipedia menciona dos para los cuales los algoritmos basados ​​en el refinamiento de la partición se ejecutan en tiempo lineal. Existe el orden topológico ordenado lexicográficamente [1] y un algoritmo para la búsqueda de amplitud lexicográfica primero [2].

¿Hay otros ejemplos o referencias a problemas que se puedan resolver usando el refinamiento de partición de manera muy eficiente, lo que significa algo mejor que loglineal en términos de tiempo?


[1] Sethi, Ravi, "Programación de gráficos en dos procesadores", SIAM Journal on Computing 5 (1): 73–82, 1976.

[2] Rose, DJ, Tarjan, RE, Lueker, GS, "Aspectos algorítmicos de la eliminación de vértices en gráficos", SIAM Journal on Computing 5 (2): 266–283, 1976.

Juho
fuente

Respuestas:

2

Algunos algoritmos de descomposición modular de tiempo lineal utilizan (algún tipo de) refinamiento de partición; consulte, por ejemplo, estos algoritmos para gráficos dirigidos y no dirigidos .

frafl
fuente
1
¿Puedes explicar un poco más sobre cómo se usa el refinamiento de partición en estos casos? De lo contrario, se ve interesante!
Juho