Algoritmos de gráfico incremental

Question

Existen muchos algoritmos de grafos básicos, como clasificación topológica, componentes fuertemente/débilmente conectados, caminos más cortos de un solo par/fuente única, alcanzabilidad, etc. Las variantes incrementales de estos algoritmos tienen una variedad de aplicaciones prácticas importantes. Por "incremental" me refiero a los algoritmos de grafos que pueden calcular pequeños cambios en sus salidas con pequeños cambios (por ejemplo, inserción y eliminación de bordes) en el gráfico de entrada sin tener que volver a calcular todo. Por ejemplo, un recolector de basura que acumula el subpunto de bloques asignados en el montón accesible desde las raíces globales. Sin embargo, no recuerdo haber visto el tema de los algoritmos de gráficos incrementales discutidos fuera de la literatura específica del dominio (por ejemplo, el nuevo libro de Richard Jones sobre GC).

¿Dónde puedo encontrar información sobre algoritmos de gráficos incrementales o, para el caso, algoritmos incrementales en general?

Answer 1

Hay un survey article por Eppstein, Galil, y Italiano desde 1999. Describirían lo que está buscando como "algoritmos completamente dinámicos"; los "algoritmos parcialmente dinámicos" se dividen en "algoritmos incrementales", que solo permiten inserciones, y "algoritmos decrementales", que solo permiten supresiones.

Más allá de eso, sospecho que tendrá que leer la literatura de investigación: solo hay un puñado de investigadores que trabajan con algoritmos de gráficos dinámicos. Debería poder encontrar artículos examinando los documentos que citan la encuesta.