有向圖的連通問題 Reachability

有向圖版本的動態資料結構，需要支援的操作有：

  • 更新類型的操作：
    • Insert(\(u, v\)): 新增一條從 \(u\) 連到 \(v\) 的邊。
    • Delete(\(u, v\)): 移除一條已存在的 \((u, v)\) 邊。
  • 查詢類型的操作：
    • Query(\(u, v\)): 詢問在當前的圖中是否 \(u\) 走得到 \(v\)，如果是的話回傳 yes。

Fully Dynamic Reachability

均攤更新時間

演算法文獻圖的種類演算法類型均攤更新時間
Amortized
Update Time		最差查詢時間
Demetrescu-Italiano1, Roditty2general確定性\(O(n^2)\)\(O(1)\)
Henzinger-King3general蒙地卡羅\(O(m\sqrt{n}\log^2n)\)\(O(n/\log n)\)
Roditty-Zwick4general確定性\(O(m\sqrt{n})\)\(O(\sqrt{n})\)
Roditty-Zwick4general蒙地卡羅\(O(m^{0.58}n)\)\(O(m^{0.43})\)
Demetrescu-Italiano5DAGs蒙地卡羅\(O(n^{1.58})\)\(O(n^{0.58})\)
Roditty-Zwick6general確定性\(O(m + n\log n)\)\(O(n)\)

最差更新時間

演算法文獻圖的種類演算法類型最差更新時間
Worst Case
Update Time		最差查詢時間
Sankowski7general蒙地卡羅\(O(n^2)\)\(O(1)\)
Sankowski7general蒙地卡羅\(O(n^{1.58})\)\(O(n^{0.58})\)
Sankowski7general蒙地卡羅\(O(n^{1.447})\)8\(O(n^{1.447})\)8
van den Brand,
Nanongkai,
Saranurak8		general蒙地卡羅\(O(n^{1.407})\)\(O(n^{1.407})\)

Incremental Reachability

演算法文獻圖的種類演算法類型更新時間最差查詢時間
Italiano9general確定性均攤 \(O(n)\)\(O(n)\)

Decremental Reachability

演算法文獻圖的種類演算法類型更新時間最差查詢時間
Frigioni, Miller,
Nanni,
Zaroliagis10		general確定性全部 \(O(m^2)\)\(O(1)\)
Roditty-Zwick4general拉斯維加斯全部 \(O(mn)\)\(O(1)\)
Łącki11general確定性全部 \(O(mn)\)\(O(1)\)

參考資料

4

Roditty and Zwick, Improved Dynamic Reachability Algorithms for Directed Graphs. SIAM J. Comput 2008.

8

van den Brand, Nanongkai, and Saranurak. Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds. FOCS 2019.

2

Liam Roditty, A Faster and Simpler Fully Dynamic Transitive Closure. SODA 2003. TALG 2008.

3

M.R. Henzinger and V. King, Fully Dynamic Biconnectivity and Transtive Closure. FOCS 1995.

10

Frigioni, Miller, Nanni, and Zaroliagis, An Experimental Study of Dynamic Algorithms for Transitive Closure, J of Experimental Algorithms 2001.