Dado um gráfico acíclico direcionado, , é possível oferecer suporte eficiente às seguintes operações?
- L um b : determina se existe um caminho em do nó para o nó
- a b G : Adiciona uma aresta de a no gráfico
- a b G : remove a aresta de para em
- : adiciona um vértice a G
- : remove um vértice de G
Algumas notas:
- Se não permitirmos , parece que seria fácil manter as informações de conexão, usando uma estrutura de dados do tipo conjunto separado.
- Obviamente, o pode ser implementado usando a pesquisa de profundidade ou largura, usando a representação ingênua do gráfico com base em ponteiro. Mas isso é ineficiente.
Espero um tempo constante ou logarítmico amortizado para as três operações. Isso é possível?
ds.algorithms
graph-algorithms
directed-acyclic-graph
online-algorithms
Justin Kilpatrick
fonte
fonte
remove
Também remove as bordas do incidente? Nesse caso, exigir que a operação seja de tempo O (log n) pode ser demais para se esperar….Respostas:
O problema que você descreveu é a acessibilidade totalmente dinâmica do DAG (também conhecido como fechamento transitivo totalmente dinâmico nos DAGs). É chamado de totalmente dinâmico, pois as pessoas também estudam as versões nas quais somente exclusões são possíveis (então é chamada de acessibilidade decremental) e onde apenas inserções são possíveis (chamadas de acessibilidade incremental).
Existem algumas vantagens e desvantagens entre o tempo de atualização e o tempo de consulta. Seja o número de arestas en o número de vértices. Para os DAGs, Demetrescu e Italiano (FOCS'00) forneceram uma estrutura de dados aleatória que suporta atualizações (inserções ou exclusões de arestas) no tempo O ( n 1,58 ) e consultas de acessibilidade no tempo O ( n 0,58 ) (inserções / exclusões de nós também são suportadas , em O (1) tempo); esse resultado foi estendido por Sankowski (FOCS'04) para trabalhar com gráficos direcionados gerais. Também para DAGs, Roditty (SODA'03) mostrou que é possível manter a matriz de fechamento transitivo no tempo total O ( m n + I · n 2 + D ), ondem n n1.58 n0.58 mn+I⋅n2+D é o número de inserções, D o número de exclusões e, claro, o tempo de consulta é O ( 1 ).I D 1
Para gráficos direcionados gerais, são conhecidos os seguintes tempos (atualização, consulta): (O ( ), O (1)) (Demetrescu e Italiano FOCS'00 (amortizado), Sankowski FOCS'04 (pior caso)) ( O ( m √n2 ),O( √mn−−√ )) (Roditty, Zwick FOCS'02), (O (m+nlogn), O (n)) (Roditty, Zwick STOC'04), (O (n 1,58 ), O (n 0,58 )) e (O (n 1.495 ), O (n 1.495 )) de Sankowski (FOCS'04).O(n−−√ m+nlogn n n1.58 n0.58 n1.495 n1.495
Obter um tempo de consulta polilogarítmica, sem aumentar muito o tempo de atualização, é um grande problema em aberto, mesmo para DAGs.
fonte
(O(1),O(n^2))
ou(O(m),O(n+m))
.Acho que os melhores resultados até agora são discutidos em "Manutenção de matrizes dinâmicas para fechamento transitivo totalmente dinâmico" . Esse artigo discute um algoritmo aleatório com tempo de consulta e tempo de atualização O ( n 1,58 ) .O(n0.58) O(n1.58)
(Isso cobre apenas a primeira versão da sua pergunta, com
link
eunlink
mas semadd
eremove
.)fonte