×

zbMATH — the first resource for mathematics

Note on the structure of Kruskal’s algorithm. (English) Zbl 1219.05181
Let \(G=(V,E)\) be a connected edge-weighted graph and let \((V,F)\) be its minimal spanning tree constructed by Kruskal’s algorithm [J.B. Kruskal jun., “On the shortest spanning subtree of a graph and the traveling salesman problem,” Proc. Am. Math. Soc. 7, 48–50 (1956; Zbl 0070.18404)]. We capture the evolution of the spanning forest from \((V,\emptyset)\) to \((V,F)\) by a rooted binary tree \(R\) with leaves in \(V\) and internal nodes in \(F\). Let \(h(G)\) denote the height of \(R\). In case of Prim’s algorithm we would have \(h(G_n) = n-1\) for every connected graph \(G_n\) on \(n\) vertices. In case of Kruskal’s algorithm there is a constant \(c>0\) such that the probability of \(h(G_n) \geq cn\) tends to \(1\) for \(n\to\infty\), and therefore the expected value of \(h(G_n)\) is in \(\Theta(n)\), for three choices of random edge-weights:
(1)
\(G_n\) is a complete graph on \(n\) independently uniformly distributed random points in \([0,1]^d\) and the edges are weighted by the Euclidean distance,
(2)
\(G_n\) is a complete graph on \(n\) vertices and the edge-weights are independently uniformly distributed in \([0,1]\),
(3)
\(G_n\) is the Cartesian product of \(d\) paths \(P_k\), \(n=k^d\), and the edge-weights are independently uniformly distributed in \([0,1]\).
MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05C80 Random graphs (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Boston (1974) · Zbl 0326.68005
[2] Aldous, D.: A random tree model associated with random graphs. Random Struct. Algorithms 4, 383–402 (1990) · Zbl 0747.05077 · doi:10.1002/rsa.3240010402
[3] Aldous, D., Steele, J.M.: Asymptotics for euclidean minimum spanning trees on random points. Probab. Theory Relat. Fields 92, 247–258 (1992) · Zbl 0767.60005 · doi:10.1007/BF01194923
[4] Bollobás, B.: Random Graphs, 2nd edn. Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (2001)
[5] Bollobás, B., Simon, I.: On the expected behavior of disjoint set union algorithms. In: STOC ’85: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 224–231. ACM, New York (1985)
[6] Bollobás, B., Simon, I.: Probabilistic analysis of disjoint set union algorithms. SIAM J. Comput. 22, 153–1074 (1993) · Zbl 0789.68069
[7] Borgs, C., Chayes, J.T., Kesten, H., Spencer, J.: The birth of the infinite cluster: Finite-size scaling in percolation. Commun. Math. Phys. 224, 153–204 (2001) · Zbl 1038.82035 · doi:10.1007/s002200100521
[8] Boruvka, O.: O jistém problému minimálním. Práce Mor. Přírodověd. Spol. v Brně (Acta Soc. Sci. Natur. Moravicae) 3, 37–58 (1926)
[9] Chernoff, H.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493–507 (1952) · Zbl 0048.11804 · doi:10.1214/aoms/1177729330
[10] Dijkstra, E.: A note on two problems in connection with graphs. Numer. Math. 1, 269–271 (1959) · Zbl 0092.16002 · doi:10.1007/BF01386390
[11] Erdos, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17–61 (1960) · Zbl 0103.16301
[12] Frieze, A.M.: On the value of a random minimum spanning tree problem. Discrete Appl. Math. 10, 47–56 (1985) · Zbl 0578.05015 · doi:10.1016/0166-218X(85)90058-7
[13] Grimmett, G.R.: Percolation, 2nd edn. A Series of Comprehensive Studies in Mathematics, vol. 321. Springer, New York (1999)
[14] Janson, S., Łuczak, T., Ruciński, A.: Random Graphs. Wiley, New York (2000)
[15] Jarńik, V.: O jistém problému minimálnim. Práce Mor. Přírodověd. Spol. v Brně (Acta Soc. Sci. Natur. Moravicae) 6, 57–63 (1930)
[16] Kesten, H.: Percolation Theory for Mathematicians. Birkhäuser, Boston (1980) · Zbl 0522.60097
[17] Knuth, D.E., Schönhage, A.: The expected linearity of a simple equivalence algorithm. Theor. Comput. Sci. 6, 281–315 (1978) · Zbl 0377.68024 · doi:10.1016/0304-3975(78)90009-9
[18] Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 2, 48–50 (1956) · Zbl 0070.18404 · doi:10.1090/S0002-9939-1956-0078686-7
[19] McDiarmid, C., Johnson, T., Stone, H.S.: On finding a minimum spanning tree in a network with random weights. Random Struct. Algorithms 10(1–2), 187–204 (1997) · Zbl 0872.60008 · doi:10.1002/(SICI)1098-2418(199701/03)10:1/2<187::AID-RSA10>3.3.CO;2-Y
[20] Meester, R., Roy, R.: Continuum Percolation. Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge (1996) · Zbl 0858.60092
[21] Penrose, M.: The longest edge of a random minimal spanning tree. Ann. Appl. Probab. 7(2), 340–361 (1997) · Zbl 0884.60042 · doi:10.1214/aoap/1034625335
[22] Penrose, M.: Random minimal spanning tree and percolation on the n-cube. Random Struct. Algorithms 12, 63–82 (1998) · Zbl 0899.60083 · doi:10.1002/(SICI)1098-2418(199801)12:1<63::AID-RSA4>3.0.CO;2-R
[23] Penrose, M.: A strong law for the longest edge of the minimal spanning tree. Ann. Probab. 27(1), 246–260 (1999) · Zbl 0944.60015 · doi:10.1214/aop/1022677261
[24] Penrose, M.: Random Geometric Graphs. Oxford Studies in Probability. Oxford University Press, Oxford (2003) · Zbl 1029.60007
[25] Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 1389–1401 (1957)
[26] Steele, J.M.: Probability Theory and Combinatorial Optimization. CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM, Philadelphia (1997) · Zbl 0916.90233
[27] Yao, A.C.: On the average behavior of set merging algorithms. In: STOC ’76: Proceedings of the 8th Annual ACM Symposium on Theory of Computing, pp. 192–195 (1976) · Zbl 0365.68034
[28] Yukich, J.E.: Probability Theory of Classical Euclidean Optimization Problems. Lecture Notes in Mathematics, vol. 1675. Springer, New York (1998) · Zbl 0902.60001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.