11
En términos de tiempo de ejecución, ¿cuál es el algoritmo de cierre transitivo más conocido para gráficos dirigidos?algoritmo de cierre transitivo más conocido para el gráfico
Actualmente estoy usando el algoritmo de Warshall pero es O (n^3). Aunque, debido a la representación gráfica, mi implementación mejora levemente (en lugar de verificar todos los bordes, solo comprueba todos los bordes). ¿Hay algún algoritmo de cierre transitivo que sea mejor que esto? En particular, ¿hay algo específicamente para las arquitecturas multiproceso de memoria compartida?
Gracias de antemano.
Raghava.
Gracias por la respuesta. Supongo que la aceleración heurística sería útil solo si hay muchos componentes fuertemente conectados en el gráfico. Necesito observar los gráficos generados por diferentes conjuntos de datos para ver si este es el caso. Pero si ese no es el caso, entonces el de Warshall es el mejor, ¿verdad? Pensé que podría haber algo más. – Raghava
Creo que el enfoque mencionado en el primer punto del primer enlace es el camino a seguir. ¡También será relativamente fácil paralelizar! –
@Tom: A partir de ahora, ya estoy usando una biblioteca de gráficos de múltiples hilos. Así que estoy usando su representación gráfica que no es una matriz. – Raghava