增量圖算法

Question

有許多基本圖算法，如拓撲排序，強/弱連接組件，全對/單源最短路徑，可達性等。這些算法的增量變體具有各種重要的實際應用。 「增量」指的是那些可以計算輸出的小變化的圖算法，只要對輸入圖進行小的變化（例如邊插入和刪除）而無需重新計算所有內容。例如，一個垃圾收集器累積堆的子圖分配塊從全局根可到達。但是，我不記得在特定領域的文獻（例如Richard Jones關於GC的新書）之外討論的增量圖算法的主題。

從哪裏可以找到關於增量圖算法的信息，或者就此而言，一般來說增量算法的信息？

Answer 1

從1999年開始Eppstein，Galil和Italiano的survey article。他們會描述你正在尋找什麼樣的「完全動態算法」。 「部分動態算法」分爲只允許插入的「增量算法」和只允許刪除的「遞減算法」。

除此之外，我懷疑你將不得不閱讀研究文獻 - 只有少數研究人員從事動態圖算法。您應該能夠通過檢查引用調查的論文來查找文章。