Note on the structure of Kruskal's algorithm

DOI10.1007/S00453-008-9164-4MaRDI QIDQ848958zbMATH OpenOpenAlexFDO

Authors Nicolas Broutin, Erin McLeish, Luc 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

random graphheightpercolationrandom treeminimal spanning treeKruskal

Mathematics Subject Classification ID

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

Recommendations

• On finding a minimum spanning tree in a network with random weights
• Successive minimum spanning trees
• On random minimum length spanning trees
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• On the value of a random minimum spanning tree problem
• scientific article; zbMATH DE number 7650127
• Random minimum length spanning trees in regular graphs
• A note on random minimum length spanning trees
• scientific article; zbMATH DE number 5730481

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3826957 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3569817 (Why is no real title available?)
• scientific article; zbMATH DE number 1123759 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A note on two problems in connexion with graphs
• A random tree model associated with random graphs
• A strong law for the longest edge of the minimal spanning tree
• Asymptotics for Euclidean minimal spanning trees on random points
• Continuum Percolation
• On finding a minimum spanning tree in a network with random weights
• On the shortest spanning subtree of a graph and the traveling salesman problem
• On the value of a random minimum spanning tree problem
• Probabilistic Analysis of Disjoint Set Union Algorithms
• Probability theory of classical Euclidean optimization problems
• Random Geometric Graphs
• The birth of the infinite cluster: Finite-size scaling in percolation
• The expected linearity of a simple equivalence algorithm
• The longest edge of the random minimal spanning tree

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q848958)