最小生成樹演算法
| 演算法文獻 | 時間複雜度 | 備註 | ||
|---|---|---|---|---|
| Dijkstra-Jarník-Prim | 確定性 | \(O(m+n\log n)\) | ||
| Kruskal | 確定性 | \(O(m\log n)\) | 排序後 \(O(m\alpha(n))\) | |
| Borůvka | 確定性 | \(O(m\log n)\) | ||
| Borůvka-Prim | 確定性 | \(O(m\log\log n)\) | ||
| Yao1 | 確定性 | \(O(m\log\log n)\) | ||
| Tarjan2 | 確定性 | \(O(m\log\log n)\) | ||
| Fredman-Tarjan3 | 確定性 | \(O(m\log^* n)\) | Fibonacci Heaps 問世 | |
| Gabow-Galil-Spencer-Tarjan4 | 確定性 | \(O(m\log\log^* n)\) | ||
| Fredman-Willard | 整數權重 | 確定性 | \(O(m)\) | |
| Karger-Klein-Tarjan5 | 期望時間 | \(O(m)\) | ||
| Chazelle6 | 確定性 | \(O(m\alpha(n))\) | ||
| Pettie-Ramachandran7 | 確定性 | 決策樹最佳的 |
驗證最小生成樹
- Tarjan 1979. \(O(m\alpha(m, n))\) Applications of path compressions on balanced trees
- Komlós 1985. 給出了只需要 \(O(m)\) 次邊權比較的演算法 Linear Verification for Spanning Trees, Combinatorica 1985.
- Dixon-Rauch-Tarjan 1992. 利用查表實作 Komlós 演算法得到 \(O(m)\) Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time.
- King 1995. 簡化了查表、給出有趣的樹分治結構 \(O(m)\) A Simpler Minimum Spanning Tree Verification Algorithm, Algorithmica, 1997.
- Hagerup 2009. 簡化了 King 的演算法當中對輕重邊的編碼部分 \(O(m)\) An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees, Graph Theoretic Concepts in Computer Science, 2009.
近似最小生成樹
- Chazelle-Rubinfeld-Trevisan 2005. Approximating the Minimum Spanning Tree Weight in Sublinear Time
參考資料
- https://www.cs.cmu.edu/~anupamg/advalgos17/scribes/lec01.pdf
- CMU Advanced Algorithms Fall 2020 課程講義，第一章
- Gregory Bint, Minimum Spanning Tree Verification, Lecture Notes, 2013.
Andrew Chi-chih Yao, An \(O(\vert E\vert \log\log \vert V\vert )\) algorithm for finding minimum spanning trees, Information Processing Letters, 1975.
Robert Endre Tarjan, Finding Minimum Spanning Trees, Technical Report, 1975.
Michael L. Fredman and Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, JACM, 1987.
H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, 1986.
David R. Karger, Philip N. Klein, and Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, JACM, 1995.
Bernard Chazelle, A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, JACM, 2000.
Seth Pettie and Vijaya Ramachandran, An optimal minimum spanning tree algorithm, JACM 2002.
Tianqi Yang, Tree Path Minimum Query Oracle via Boruvka Trees, ArXiv 2021.
直接應用的文章
- MST on Minor-Closed Graphs 是線性時間：https://www.emis.de/journals/AM/04-3/am1139.pdf (可以理解，因為 Minor-Closed Graphs 是稀疏圖，永遠有 \(m=O(n)\)。)
- MST on High Girth 是線性時間：https://www.cs.utexas.edu/~danama/papers/mst/high-girth.pdf (居然沒有發表過...，這篇傳達的概念是說，從 graph girth 去解決 MST 可能是希望渺茫的：如果有常數腰圍的線性時間演算法，就能有真正的線性時間演算法。)