Fechamento transitivo on-line melhor que O (N ^ 2) por adição de borda

15

Estou procurando um algoritmo on-line para manter o fechamento transitivo de um gráfico acíclico direcionado com uma complexidade de tempo menor que O (N ^ 2) por adição de aresta. Meu algoritmo atual é assim:

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

Para arestas O (N ^ 2), isso traduz em uma complexidade total de tempo de O (N ^ 4) muito pior do que, por exemplo, Floyd-Warshall .

Alexandru
fonte

Respostas:

15

O (n) tempo por adição de aresta:

Jukka Suomela
fonte
2
Veja também: DM Yellin. Acelerando o fechamento transitivo dinâmico para gráficos de graus delimitados. Acta Informatica, 30: 369-384, 1993.
Jeffε 16/08/10
11
O primeiro artigo fornece duas operações importantes a partir do fechamento transitivo, mas eu preciso de uma terceira: iterando por todos os nós acessíveis. O segundo artigo é bom, no entanto.
Alexandru