Qual é o algoritmo determinístico mais rápido para a acessibilidade dinâmica do dígrafo sem exclusão de borda?

16

Qual é o melhor resultado determinístico para manter o fechamento transitivo dinâmico em um gráfico direcionado com apenas inserção de arestas?

Li alguns artigos sobre o problema do fechamento transitivo dinâmico com inserção e exclusão de bordas. No entanto, existem algoritmos melhores para isso com apenas inserção de arestas?

ds.algorithms graph-theory graph-algorithms dynamic-algorithms wei wang
fonte
3
Isso não é resolvido pela estrutura de dados de união de localização?
Tyson Williams
Seu gráfico é direcionado ou não direcionado? @TysonWilliams está correto em que, para gráficos sem direção sem exclusões borda, você está basicamente fazendo encontrar a união (cada inserção é uma operação UNION)
Suresh Venkat
11
Ah .. esqueci de mencionar, é um dígrafo. Meu mal .... será atualizado então.
wei wang

Respostas:

9

O(n)

virgi
fonte