Determinación de la conectividad para un gráfico completamente dinámico con inserción y eliminación de vértices / subgrafos

8

Estoy buscando una solución al siguiente problema y me pregunto si alguien podría señalarme alguna investigación existente sobre este tema. Vengo de una aplicación de gráficos del mundo real, así que tengan paciencia conmigo si mi terminología no es exactamente la correcta.

Tengo un sistema de base de datos donde el usuario puede agregar / eliminar / mover objetos creando / eliminando y alterando las relaciones. Como tal, puedo ver los objetos como vértices en un gráfico y las relaciones como bordes y bordes se pueden ponderar según el tipo de relaciones (composición, asociación o agregación).

Desde el punto de vista del usuario, agregar un nuevo elemento puede ser un solo clic y debajo del capó, el programa crea un gráfico de objetos vinculados por relaciones. Este gráfico, luego se agrega al gráfico principal que define la base de datos completa. Eliminar un elemento sería el reverso donde los enlaces / bordes están desconectados y el gráfico se convierte en dos gráficos disjuntos donde 1 es la base de datos, y el otro consiste en vértices formados por el elemento y sus subelementos.

Necesito una forma realmente rápida de determinar cuándo tengo gráficos disjuntos y cuándo 2 gráficos disjuntos se convierten en 1 nuevamente. Eché un breve vistazo a Holm, de Lichtenberg y Thorup ( 2001 ; pdf ). Parece el camino a seguir, pero el autor mencionó que solo están considerando un gráfico con un número fijo de vértices. Solo me pregunto si los algoritmos generalmente se extienden a la adición / eliminación de vértices simplemente realizando la adición de bordes de forma incremental ¿O ha habido trabajos que se adaptan específicamente para tal escenario?

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

Respuestas:

4

Esta no es una pregunta trivial en absoluto. Uno de los problemas que tendrá para encontrar algoritmos para esto es la desconexión (juego de palabras) del trabajo en gráficos dinámicos. El trabajo de Thorup et al. (El que usted menciona) es probablemente el mejor comienzo para el tipo de cosas que está buscando.

También puedes probar Bhadra & Ferreira , probablemente están un poco fuera de tema para lo que quieres, pero tienen referencias a otro material que podría ser útil.

Luke Mathieson
fuente
1

Las actualizaciones de Vertex se pueden manejar usando actualizaciones de borde de la siguiente manera (aunque un poco ineficiente ya que hace que deg (u) llame a la función de actualización de borde):

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 y col. El análisis del tiempo de ejecución de Al indica que su tiempo de actualización es tiempo amortizado por actualización perimetral. Entonces, no implica directamente ningún poli. resultado del tiempo de actualización logarítmica en las actualizaciones de vértice.

Hay algunos trabajos en los que la operación de actualización también admite la eliminación de vértices / adiciones. En [1] para el problema de las rutas más cortas de todos los pares dinámicos, básicamente permiten actualizar los bordes incidentes en un vértice especificando los nuevos pesos. Podemos actualizarlos a + infinito para eliminar un vértice y de manera similar para agregar un vértice.

Puede encontrar las referencias [2] y [3] útiles si recién comienza con algoritmos de gráficos dinámicos. [2] da una buena idea de alto nivel de los enfoques actuales para el problema de conectividad dinámica.

Referencias

  1. Un nuevo enfoque dinámico Todos los pares de caminos más cortos, Demetrescu. et. Al, JACM 2004 Voume 51 número 6, 2004

  2. Diapositiva de la charla sobre algoritmos de gráficos dinámicos por el Dr. Surender Baswana en el taller "Avances recientes en estructuras de datos y algoritmos" realizado en el IMSc, Chennai.

  3. Camil Demetrescu y Pino Italiano, Gráficos dinámicos, Manual sobre estructuras y aplicaciones de datos, Capítulo 36. Dinesh Mehta y Sartaj Sahni (eds.), CRC Press Series, en Computer and Information Science, enero de 2005. [Borrador (pdf)]

rizwanhudda
fuente