增量式图算法

Question

增量式图算法

9

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

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

- J D

2

“incremental”和“dynamic”是一样的吗？ - mishadoff

@mishadoff：显然是这样。 :-) - J D

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- not for show · Accepted Answer

有一篇来自1999年Eppstein, Galil和Italiano撰写的调查文章。他们将您要寻找的内容描述为“完全动态算法”；“部分动态算法”被分为“增量算法”，它们仅允许插入操作，以及“减量算法”，它们仅允许删除操作。

此外，我怀疑您需要阅读研究文献-只有少数研究人员从事动态图算法的研究。通过检查引用该调查的论文，您应该能够找到相关文章。