Note on the structure of Kruskal's algorithm

DOI10.1007/s00453-008-9164-4zbMath1219.05181OpenAlexW2151957880MaRDI QIDQ848958

Erin McLeish, Nicolas Broutin, Luc P. Devroye

Publication date: 23 February 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9164-4

zbMATH Keywords

heightpercolationrandom graphrandom treeminimal spanning treeKruskal

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• On the value of a random minimum spanning tree problem
• Asymptotics for Euclidean minimal spanning trees on random points
• The expected linearity of a simple equivalence algorithm
• The longest edge of the random minimal spanning tree
• Probability theory of classical Euclidean optimization problems
• A strong law for the longest edge of the minimal spanning tree
• On finding a minimum spanning tree in a network with random weights
• Probabilistic Analysis of Disjoint Set Union Algorithms
• A random tree model associated with random graphs
• Random Geometric Graphs
• Continuum Percolation
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• The birth of the infinite cluster: Finite-size scaling in percolation

This page was built for publication: Note on the structure of Kruskal's algorithm