Existe um algoritmo online para acompanhar os componentes em um gráfico não direcionado em mudança?

12

Problema

Eu tenho um gráfico não direcionado (com várias arestas), que mudará com o tempo, nós e arestas podem ser inseridos e excluídos. Em cada modificação do gráfico, eu tenho que atualizar os componentes conectados deste gráfico.

Propriedades

As propriedades adicionais são que nunca dois componentes serão reconectados. Obviamente, o gráfico pode ter ciclos para uma quantia arbitrária (caso contrário, a solução seria trivial). Se uma aresta não contiver um nó n , nunca adotará esse nó. No entanto, se n e , ele pode mudar para n e .ennene

Abordagens

Até agora, tenho duas abordagens possíveis, mas como você verá, elas são horríveis:

Lento sem estado

Posso pesquisar (dfs / bfs) o gráfico a partir do (s) elemento (s) modificado (s) toda vez. Isso economiza espaço, mas é lento, pois temos O (n + m) para cada modificação.

Abordagem rápida com estado (-er) (?)

Posso armazenar todos os caminhos possíveis para cada nó em todos os nós possíveis, mas se eu o vir corretamente, isso consumirá memória O (n ^ 4). Mas não tenho certeza de como é a melhoria do tempo de execução (se houver uma, porque preciso manter as informações atualizadas para cada nó no mesmo componente).

Questão

Você tem alguma dica, como posso aprender mais sobre esse problema ou talvez sobre alguns algoritmos em que posso desenvolver?

Nota

Se houver uma grande melhoria no tempo de execução / memória, eu poderia viver com uma solução não ideal que às vezes diz que dois componentes são um, mas é claro que eu preferiria uma solução ideal.

bitmask
fonte
Se eu li corretamente suas duas últimas frases em "Propriedades", parece que você está interessado apenas no problema decrescente. Nesse caso, verifique o trabalho de Thorup sobre conectividade dinâmica decremental. (Você pode encontrar a citação via ponteiros de Jeffe, que são para a versão totalmente dinâmica do problema.)
Maverick Woo
@ Maverick Woo: sempre pode haver novas arestas / nós. Eu acho que a última propriedade não é muito forte, exatamente por esse motivo. Ainda se qualifica como decremental?
bitmask
Ops, não sei como perdi a primeira frase ... Veja a "resposta" abaixo.
Maverick Woo

Respostas:

17

Existem várias estruturas de dados que suportam inserções de bordas, exclusões de bordas e consultas de conectividade (esses dois vértices estão no mesmo componente conectado?) Em tempo polilogarítmico.

Jeffε
fonte
Isso parece incrível, quando eu terminar os papéis, provavelmente vou aceitar isso.
bitmask
6

Eu acho que você está procurando o que é chamado de algoritmo de gráfico dinâmico para decomposição de componentes conectados. O algoritmo de Holm, de Lichtenberg e Thorup [HLT01] amortizou o tempo polilogarítmico em cada atualização de borda. Faz muito tempo que não olhei o problema da última vez, então provavelmente há um progresso mais recente.

[HLT01] Jacob Holm, Kristian de Lichtenberg e Mikkel Thorup. Algoritmos totalmente dinâmicos determinísticos polia logarítmicos para conectividade, spanning tree mínimo, 2 arestas e biconectividade. Journal of the ACM , 48 (4): 723–760, julho de 2001. http://doi.acm.org/10.1145/502090.502095

Tsuyoshi Ito
fonte
Jinx. Você me deve uma coca.
Jeffε
@ Jeff: Eu não sabia sobre esse jogo . Mas de acordo com as regras, eu não perdi o jogo (estou apenas no estado de "azarado"), então não lhe devo uma coca-cola a menos que fale mais ... oh, espere um momento.
Tsuyoshi Ito
se você pudesse trocar pontos de reputação :)
Suresh Venkat
5

(Por enquanto, deixe-me ficar com as consultas de conectividade, que infelizmente podem não ser suficientes para o seu aplicativo.)

Muitos dos trabalhos anteriores sobre o problema de conectividade dinâmica estão no modelo de atualização de borda: você assume que o número de vértices é fixo e pode inserir e / ou excluir bordas enquanto faz consultas. Se você só pode inserir (excluir), é incremental (decremental). Se você pode fazer as duas coisas, é totalmente dinâmico. O trabalho de Thorup, como apontado por JeffE (e eu no comentário), é para atualizações de ponta.

AFAIK, a comunidade da teoria do CS está apenas começando a procurar atualizações de vértices para gráficos gerais. Houve um trabalho inovador sobre Chan, Pătraşcu e Roditty no FOCS 2008. Consulte este link para uma revisão muito recente (setembro de 2010) e as referências.

Maverick Woo
fonte
Por que você acha que o Holm et. al. abordagem não funciona para o meu problema? Eu ia adotá-lo.
bitmask
1
Se o seu gráfico tiver um grau limitado, em teoria você poderá emular uma atualização de vértice usando várias atualizações de borda. Caso contrário, uma única atualização de vértice (por exemplo, a remoção do centro de um gráfico em estrela) pode alterar drasticamente a conectividade do gráfico e, nesse caso, você precisa do resultado de Chan et al.
Maverick Woo
Entendo. Eu deveria ter declarado na pergunta original, que as remoções de vértices são raras, para que eu possa me dar ao luxo de fazê-lo, borda a borda.
bitmask