¿Cuál es el algoritmo determinista más rápido para el alcance dinámico del dígrafo sin eliminación de bordes?

¿Cuál es el mejor resultado determinista para mantener el cierre transitivo dinámico en un gráfico dirigido con solo inserción de borde?

Leí algunos documentos sobre el problema de cierre transitivo dinámico con inserción y eliminación de bordes. Sin embargo, ¿hay algún algoritmo mejor para eso con solo inserción de borde?

ds.algorithms graph-theory graph-algorithms dynamic-algorithms wei wang
fuente

¿No se resuelve esto mediante la estructura de datos union-find?

Tyson Williams el

¿Su gráfico está dirigido o no dirigido? @TysonWilliams es correcto porque para los gráficos no dirigidos sin eliminaciones de bordes, básicamente solo está haciendo la búsqueda de unión (cada inserción es una operación UNION)

Suresh Venkat

Ah ... olvidé mencionar, es un dígrafo. Mi mal ... se actualizará entonces.

wei wang

Respuestas:

$O(n)$

virgi
fuente