Note on the structure of Kruskal's algorithm
From MaRDI portal
Publication:848958
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
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
