增量图算法

Question

有许多基本的图算法，如拓扑排序、强/弱连通分支、所有对/单源最短路径、可达性等。这些算法的增量变体具有各种重要的实际应用。我所说的“增量”是指那些可以在给定输入图的小更改(例如边插入和删除)的情况下计算其输出的小更改的图算法，而不必重新计算所有内容。例如，垃圾收集器累积从全局根可达的堆分配块的子图。然而，我不记得在特定领域的文献(例如Richard Jones关于GC的新书)之外讨论过增量图算法的主题。

我在哪里可以找到关于增量图算法的信息，或者，就这一点而言，一般的增量算法？

Answer 1

这里有一本由埃普斯坦、加里尔和意大利于1999年创作的survey article。它们会将您正在寻找的内容描述为“完全动态算法”；“部分动态算法”分为“增量算法”和“减量算法”，前者只允许插入，后者只允许删除。

除此之外，我怀疑您将不得不阅读研究文献-只有少数研究人员致力于动态图算法。你应该能够通过查看引用调查的论文来找到文章。