¿Existe un algoritmo en línea para realizar un seguimiento de los componentes en un gráfico no dirigido cambiante?

12

Problema

Tengo un gráfico no dirigido (con múltiples bordes), que cambiará con el tiempo, los nodos y los bordes se pueden insertar y eliminar. En cada modificación del gráfico, tengo que actualizar los componentes conectados de este gráfico.

Propiedades

Las propiedades adicionales son que no se volverán a conectar dos componentes. Obviamente, el gráfico puede tener ciclos a una cantidad arbitraria (de lo contrario, la solución sería trivial). Si un borde no contiene un nodo n , nunca adoptará ese nodo. Sin embargo, si n ∈ e , puede cambiar a n ∉ e .enn∈en∉e

Enfoques

Tengo dos enfoques posibles hasta ahora, pero como verán, son horribles:

Lento sin estado

Puedo buscar (dfs / bfs) el gráfico a partir de los elementos modificados cada vez. Esto ahorra espacio, pero es lento ya que tenemos O (n + m) para cada modificación.

Enfoque rápido (-er) (?) Con estado

Puedo almacenar todas las rutas posibles para cada nodo a todos los nodos posibles, pero si lo veo correctamente, esto tomará O (n ^ 4) memoria. Pero no estoy seguro de cómo es la mejora del tiempo de ejecución (si es que hay una, porque tengo que mantener la información actualizada para cada nodo en el mismo componente).

Pregunta

¿Tiene alguna sugerencia, cómo puedo aprender más sobre ese problema o quizás algunos algoritmos sobre los que puedo construir?

Nota

Si hay una gran mejora en el tiempo de ejecución / memoria, podría vivir con una solución no óptima que a veces dice que dos componentes son uno, pero, por supuesto, preferiría una solución óptima.

ds.algorithms graph-theory approximation-algorithms online-algorithms máscara de bits
fuente
Si leí bien tus dos últimas oraciones en "Propiedades", entonces parece que estás interesado solo en el problema decremental. Si es así, asegúrese de revisar el trabajo de Thorup sobre conectividad dinámica decreciente. (Puede encontrar la cita a través de los punteros de JeffE, que son para la versión completamente dinámica del problema).
Maverick Woo,
@Maverick Woo: Siempre puede haber nuevos bordes / nodos. Creo que la última propiedad no es muy fuerte, exactamente por esta razón. ¿Todavía califica como decremental?
bitmask
Vaya, no sé cómo me perdí la primera oración ... Vea la "respuesta" a continuación.
Maverick Woo

Respuestas:

17

Hay varias estructuras de datos que admiten inserciones de bordes, eliminaciones de bordes y consultas de conectividad (¿están estos dos vértices en el mismo componente conectado?) En tiempo pollogarítmico.

Jeffε
fuente
Esto suena increíble, una vez que haya terminado los periódicos, probablemente lo acepte.
máscara de bits
6

Creo que está buscando lo que se llama el algoritmo de gráfico dinámico para la descomposición de componentes conectados. El algoritmo de Holm, de Lichtenberg y Thorup [HLT01] ha amortizado el tiempo pollogarítmico en cada actualización de borde. Ha pasado mucho tiempo desde que examiné el problema la última vez, por lo que probablemente haya un progreso más reciente.

[HLT01] Jacob Holm, Kristian de Lichtenberg y Mikkel Thorup. Algoritmos determinísticos polilogarítmicos totalmente dinámicos para conectividad, árbol de expansión mínimo, 2 bordes y biconnectividad. Journal of the ACM , 48 (4): 723–760, julio de 2001. http://doi.acm.org/10.1145/502090.502095

Tsuyoshi Ito
fuente
Gafe. Me debes una coca cola.
Jeffε
@JeffE: No sabía sobre ese juego . Pero de acuerdo con las reglas, no he perdido el juego (solo estoy en el estado de "mala suerte"), así que no te debo una coca a menos que hable más ... oh, espera un momento.
Tsuyoshi Ito
si solo pudieras intercambiar puntos de reputación :)
Suresh Venkat
5

(Por ahora, permítanme seguir con las consultas de conectividad, que desafortunadamente pueden no ser suficientes para su aplicación).

Gran parte del trabajo anterior sobre el problema de la conectividad dinámica está en el modelo de actualización de bordes: se supone que el número de vértices es fijo, y se pueden insertar y / o eliminar bordes al realizar consultas. Si solo puede insertar (eliminar), eso es incremental (decremental). Si puede hacer ambas cosas, eso es completamente dinámico. El trabajo de Thorup como lo señaló JeffE (y yo en el comentario) son para actualizaciones de borde.

AFAIK, la comunidad de teoría CS solo está comenzando a buscar actualizaciones de vértices para gráficos generales. Chan, Pătraşcu y Roditty realizaron un trabajo innovador al respecto en FOCS 2008. Consulte este enlace para obtener una revisión muy reciente (septiembre de 2010) y las referencias que contiene.

Maverick Woo
fuente
¿Por qué crees que Holm et. Alabama. enfoque no funciona para mi problema? Iba a adoptarlo.
bitmask
1
Si su gráfico tiene un grado acotado, entonces, en teoría, puede emular una actualización de vértice utilizando un montón de actualizaciones de borde. De lo contrario, una única actualización de vértice (por ejemplo, la eliminación del centro de un gráfico de estrella) puede cambiar drásticamente la conectividad del gráfico, y en ese caso necesita el resultado de Chan et al.
Maverick Woo
Veo. Debería haber declarado en la pregunta original, que las eliminaciones de vértices son raras, por lo que puedo permitirme hacerlo borde por borde.
bitmask