無向圖的連通問題 Connectivity

型態一:基本詢問

  • 更新類型操作:
    • Insert(u, v): 插入一條 \((u, v)\) 邊。
    • Delete(u, v): 刪除一條 \((u, v)\) 邊。
  • 查詢類型操作:
    • Query(u, v): 詢問 \(u\) 與 \(v\) 之間是否為 \(k\)-點連通 或 \(k\)-邊連通的。
演算法文獻\(k\)更新方式演算法類型更新查詢
Eppstein, Galil, Italiano, and Nissenzweig1\(1\)-連通Fully確定性最差 \(O(\sqrt{n})\)

型態二:整體詢問

  • 更新類型操作:
    • Insert(u, v): 插入一條 \((u, v)\) 邊。
    • Delete(u, v): 刪除一條 \((u, v)\) 邊。
  • 查詢類型操作:
    • Query(): 詢問圖 \(G\) 是否為 \(k\)-點連通 或 \(k\)-邊連通的。
演算法文獻\(k\)更新方式演算法類型更新查詢
Eppstein et al1\(2\)-點連通Fully確定性最差 \(O(n)\)
Eppstein et al1\(3\)-點連通Fully確定性最差 \(O(n)\)
Eppstein et al1\(4\)-點連通Fully確定性最差 \(O(n\alpha(n))\)
Eppstein et al1\(2\)-邊連通Fully確定性最差 \(O(\sqrt{n})\)
Eppstein et al1\(3\)-邊連通Fully確定性最差 \(O(n^{2/3})\)
Eppstein et al1\(4\)-邊連通Fully確定性最差 \(O(n\alpha(n))\)
Eppstein et al1\(\ge 5\)-邊連通Fully確定性最差 \(O(n\log n)\)

型態三:容錯模型

動態子圖連通問題

點容錯模型

1

David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig, Sparsification-A Technique for Speeding Up Dynamic Graph Algorithms, JACM 1997.