algorithm - 增量图算法

Question

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

我在哪里可以找到有关增量图算法或一般增量算法的信息？

Answer 1

有一个 survey article由 Eppstein、Galil 和 Italiano 于 1999 年提出。他们会将您正在寻找的东西描述为“全动态算法”； “部分动态算法”分为只允许插入的“增量算法”和只允许删除的“减量算法”。

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