Determinando a conectividade para um gráfico totalmente dinâmico com inserção e exclusão de vértices / subgráficos

8

Estou procurando uma solução para o seguinte problema e me pergunto se alguém poderia me indicar alguma pesquisa existente sobre esse tópico. Como venho de uma aplicação de gráfico no mundo real, tenha paciência comigo se minha terminologia não estiver exatamente correta.

Eu tenho um sistema de banco de dados onde o usuário pode adicionar / remover / mover objetos criando / excluindo e alterando relacionamentos. Como tal, posso ver os objetos como vértices em um gráfico e os relacionamentos com arestas e arestas podem ser ponderadas dependendo do tipo de relacionamento (composição, associação ou agregação).

Do ponto de vista do usuário, adicionar um novo elemento pode ser um único clique e, sob o capô, o programa cria um gráfico de objetos vinculados por relacionamentos. Este gráfico é então adicionado ao gráfico principal que define todo o banco de dados. A remoção de um elemento seria o inverso onde os links / arestas são desconectados e o gráfico se torna dois gráficos separados, onde 1 é o banco de dados e o outro consiste em vértices formados pelo elemento e seus subelementos.

Eu preciso de uma maneira muito rápida de determinar quando eu tenho gráficos disjuntos e quando 2 gráficos disjuntos se tornam 1 novamente. Dei uma breve olhada em Holm, de Lichtenberg e Thorup ( 2001 ; pdf ). Parece o caminho a seguir, mas o autor mencionou que eles estão apenas considerando um gráfico com número fixo de vértices. Apenas imaginando, os algoritmos geralmente se estendem à adição / remoção de vértices apenas executando a adição de arestas de forma incremental? Ou houve trabalhos personalizados especificamente para esse cenário?

ds.algorithms graph-theory dynamic-algorithms Thuan Seah Tan
fonte

Respostas:

4

Esta não é uma pergunta trivial. Um dos problemas que você encontrará para encontrar algoritmos é a desconexão (trocadilhos) do trabalho em gráficos dinâmicos. O trabalho de Thorup et al. (O que você mencionou) é provavelmente o melhor começo para o tipo de coisa que você está procurando.

Você também pode tentar Bhadra & Ferreira , eles provavelmente estão ficando um pouco fora do assunto para o que você quer, mas eles têm referências a outros materiais que podem ser úteis.

Luke Mathieson
fonte
1

As atualizações do Vertex podem ser manipuladas usando as atualizações de borda da seguinte maneira (embora um pouco ineficiente, pois faz deg (u) chamadas para a função de atualização de borda):

AddVertex(G,u,Adj(u)):- 
  /* Adj(u) is the vertices adjacent to u after adding u */  
  For each v in Adj(u) do 
    AddEdge(G, (u,v))

DeleteVertex(G,u):- 
  For each v in Adj(u) do
    DeleteEdge(G, (u,v))

Thorup et. A análise do tempo de execução de Al indica que o tempo de atualização é o tempo amortizado por atualização de borda. Portanto, isso não implica diretamente nenhum poli. resultado do tempo de atualização logarítmica em atualizações de vértice.

Existem alguns trabalhos em que a operação de atualização também suporta a exclusão de vértice / adição. Em [1] para o problema Dynamic All Pairs Shortest Paths, eles basicamente permitem a atualização de arestas incidentes em um vértice, especificando os novos pesos. Podemos atualizá-los todos para + infinito para excluir um vértice e da mesma forma para adicionar um vértice.

Você pode achar as referências [2] e [3] úteis se você está apenas começando com algoritmos de gráficos dinâmicos. [2] fornece uma boa idéia de alto nível das abordagens atuais para o problema de conectividade dinâmica.

Referências

  1. Uma nova abordagem à dinâmica Todos os pares de caminhos mais curtos, o Demetrescu. et. Al, JACM 2004 Voume 51 edição 6, 2004

  2. Slide da palestra sobre algoritmos de gráficos dinâmicos do Dr. Surender Baswana no workshop "Avanços recentes em estruturas e algoritmos de dados", realizado no IMSc, Chennai.

  3. Camil Demetrescu e Pino Italiano, Gráficos dinâmicos, Manual sobre estruturas e aplicativos de dados, Capítulo 36. Dinesh Mehta e Sartaj Sahni (eds.), CRC Press Series, em Computer and Information Science, janeiro de 2005. [Draft (pdf)]

rizwanhudda
fonte