Онлайн транзитивное замыкание лучше, чем O (N ^ 2) на каждое добавление ребра

Я ищу онлайновый алгоритм для поддержания транзитивного замыкания ориентированного ациклического графа с временной сложностью меньше, чем O (N ^ 2) на каждое добавление ребра. Мой текущий алгоритм выглядит так:

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

Для O (N ^ 2) ребер это приводит к общей сложности времени O (N ^ 4), что намного хуже, чем, например, у Флойда-Варшалла .

O (n) время на добавление ребра:

• GF Italiano (1986): Амортизированная эффективность структуры данных поиска пути , Теоретическая информатика 48, 273–281.

• JA La Poutré и J. van Leeuwen (1988): поддержание переходных замыканий и переходных сокращений графов , Proc. РГ 1987 .