An Optimal Minimum Spanning Tree Algorithm

Presentation on theme: "An Optimal Minimum Spanning Tree Algorithm"— Presentation transcript:

1 An Optimal Minimum Spanning Tree Algorithm
Seth Pettie and Vijaya Ramachadran Journal of the ACM Vol. 49, No. 1 January 2002, pp

2 Outline Preliminary Overview of the Algorithm
Cut and Cycle DJP Algorithm MST in Dense Case Overview of the Algorithm Key Lemma and the Partition Algorithm Decision Tree Conclusion

3 Overview of the Algorithm
Precompute the optimal decision trees for all graphs with ≤ log(3) n vertices Partition the original graph into small subgraphs soft heap Find the MST of each subgraph decision tree Use the small MSTs to construct the MST of the original graph dense case

4 G

5 GM C5 C1 C4 C6 C2 C7 C3

6 GM Partition(G,r,; M,C) 將問題分成 Ci裡面 & Ci外面 以DecisionTree求MSF C1 C2 C3

7 GM Partition(G,r,; M,C) 將問題分成 Ci裡面 & Ci外面 以DenseCase求MSF

8 Boruvka2: 將vertex數降為1/4 Gc: m降為1/4 OptimalMSF(Gc)

9 Key Lemma Lemma 3.2 Let M be a set of edges in a graph G. If C is a subgraph of G that is DJP-contractible w.r.t. GM, then MSF(G) is a subset of DJP-contractible w.r.t GM 即：在G上，使用SoftHeap， 以Prim algorithm長出來的子圖 Mc : corrupted edges with one endpoint in C Why can we decompose the MST problem like this?

10 欲證明： 證法： (1) (2) 要證明在(1)裡的每條edge， 在(2)都會存在 證明在(2)中不存在的edge， 也必不存在(1)
把(2)再拆成兩部分來看 a) In C, if an edge eMSF(C), then eMSF(G) b) In G\C, if an edge eMSF(G\CMC)MC, then eMSF(G) G C

11 In C, if an edge eMSF(C), then eMSF(G)
證明： eMSF(C) e must be the heaviest edge on some cycle in C. (cycle property) Such a cycle exists in G as well. So eMSF(G) G C

12 In G\C, if an edge eMSF(G\CMC)MC, then eMSF(G)
b) 欲證明： In G\C, if an edge eMSF(G\CMC)MC, then eMSF(G) 證明： Let H=G\CMC, show that no edge in HMSF(H) is in MSF(G) Let eHMSF(H) e is the heaviest edge on some cycle  in H. 若  不包含C contract形成的那個點 若  包含C contract形成的那個點 (見下頁) 目標：證明 e is also the heaviest edge on a cycle in G  eMSF(G) G   C

13 證明 (續上頁)： 目標：證明 e is also the heaviest edge on a cycle in G  eMSF(G)
2. 若  包含C contract形成的那個點 x, y, w, z: nodes (x,w) and (y,z): end edges of path P Since H includes no corrupted edges with on point in C, so: G-weight of these edges = (GM)-weight T: the spanning tree of CM Q: the path in T connecting x and y g: the heaviest edge in Q. w(e) > max(w(x,w), w(y,z)) (def. of e) > (GM)-weight of g (Lemma 2.1)  G-weights of all edges in Q. So, w.r.t. G-weights, e is the heaviest edge on a cycle PQ and cannot be in MSF(G). P w x e C Q y z

14 選定一個點為起點， 用DJP演算法長component Ci
長到 大於maxsize, 或 連到別的component Ci 就停下來 insert edges to Soft Heap

15 Partition & Key Lemma By applying Key Lemma repeatedly, we see that after Ci is built, the MSF of G is a subset of

16 Decision Trees 一個Decision Tree為一rooted tree，在每個internal node上都含有某些條件判斷式，不同的分支代表判斷式不同的結果。所有leaves各自代表了不同的決策，而自root到一leaf之間所經過的path即代表選擇此決策所需要的條件。

17 An Example of Decision Trees

18 MSF Decision Trees 每個internal node of MSF Decision Trees上的判斷式是一個edge-weight comparison（對於給定的graph G）。 每個internal node of MSF Decision Trees必恰好有兩個children，分別代表該edge-weight comparison為true或false。 MSF Decision Trees的leaves列出所有符合root到每一leaf之路徑上判斷式及其結果的一些spanning tree。

19 MSF Decision Trees (cont.)
Correct MSF Decision Trees的條件為每一條從root到一個leaf的path可決定唯一的一個spanning tree為G的MSF。 Optimal MSF Decision Tree的條件為沒有比之深度更小的Correct MSF Decision Tree of G存在。 當我們有graph G的Optimal MSF Decision Trees，我們就可以將G的edge weight值代入其判斷式找出其MSF。

20 An Example of MSF Decision Tree

21 Find Optimal Decision Trees
簡單的說，是用brute force search (BFS) 去暴力搜尋所有可能性並驗證。 分析當我們要找出所有具r個vertices的graph之Optimal Decision Trees的時間複雜度： 因此若取 則整個處理為o(n) time。

22 Complexity 除了recursive的部分以外，這個演算法顯然是linear time

23 If T*(m,n) = O(m), then T(m,n)=O(m)
Observations: If T*(m,n) = O(m), then T(m,n)=O(m) T(m,n)=O(T*(m,n)) for many natural functions for T* (including m(m,n)) Prove that: T(m,n)=O(T*(m,n)) holds, no matter what describing O(T*(m,n)) 除了recursive的部分以外，這個演算法顯然是linear time

24 Observations: If T*(m,n) = O(m), then T(m,n)=O(m) T(m,n)=O(T*(m,n)) for many natural functions for T* (including m(m,n)) Prove that: T(m,n)=O(T*(m,n)) holds, no matter what describing O(T*(m,n)) (Skip many propositions , lemmas and corollaries)