Cierre transitivo en línea mejor que O (N ^ 2) por adición de borde

Estoy buscando un algoritmo en línea para mantener el cierre transitivo de un gráfico acíclico dirigido con una complejidad temporal menor que O (N ^ 2) por adición de borde. Mi algoritmo actual es así:

For every new edge u->v connect all nodes in Pred(u) \cup { u } with all nodes in Succ(v) \ \cup { v }.

Para los bordes O (N ^ 2) esto se traduce en una complejidad de tiempo total de O (N ^ 4) que es mucho peor que, por ejemplo, Floyd-Warshall .

O (n) tiempo por adición de borde:

• GF Italiano (1986): eficiencia amortizada de una estructura de datos de recuperación de ruta , Theoretical Computer Science 48, 273–281.

• JA La Poutré y J. van Leeuwen (1988): Mantenimiento de cierres transitivos y reducciones transitivas de gráficos , Proc. GT 1987 .