Algorithmes de graphe incrémental

Question

Il existe de nombreux algorithmes de base de graphe, tels que le tri topologique, les composants fortement/faiblement connectés, les chemins les plus courts pour toutes les paires/toutes sources, l'accessibilité, etc. Les variantes incrémentales de ces algorithmes ont une variété d'applications pratiques importantes. Par "incrémental", j'entends ces algorithmes de graphe qui peuvent calculer de petits changements à leurs sorties en donnant de petits changements (par exemple insertion et suppression de bord) au graphe d'entrée sans avoir à tout recalculer. Par exemple, un garbage collector accumule le sous-graphe des blocs alloués par heap accessibles depuis les racines globales. Cependant, je ne me souviens pas avoir vu le sujet des algorithmes de graphes incrémentaux discutés en dehors de la littérature spécifique au domaine (par exemple le nouveau livre de Richard Jones sur GC). Où puis-je trouver des informations sur les algorithmes de graphe incrémental ou, d'ailleurs, sur les algorithmes incrémentaux en général?

Answer 1

Il y a un survey article par Eppstein, Galil et Italiano à partir de 1999. Ils décriraient ce que vous cherchez comme "algorithmes entièrement dynamiques"; Les "algorithmes partiellement dynamiques" sont divisés en "algorithmes incrémentaux", qui ne permettent que des insertions, et "algorithmes décrémentiels", qui ne permettent que des suppressions. Au-delà de cela, je suppose que vous allez devoir lire la littérature de recherche - il y a seulement une poignée de chercheurs qui travaillent sur des algorithmes de graphes dynamiques. Vous devriez être en mesure de trouver des articles en examinant les documents qui citent l'enquête.