A randomized linear-time algorithm to find minimum spanning trees

1995/03/01 by David R. Karger, Philip N. Klein, Robert E. Tarjan · 406 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Combinatorics #Computer science #Data Management and Algorithms #Data Mining Algorithms and Applications #Distributed minimum spanning tree #Euclidean minimum spanning tree #Graph #Kruskal's algorithm #Mathematics #Minimum spanning tree #Prim's algorithm #Randomized algorithm #Reverse-delete algorithm #Spanning tree #Time complexity

paper · pdf · doi:10.1145/201019.201022

published in Journal of the ACM 42(2), 321-328 (Association for Computing Machinery)

openalex publication_date 1995/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25

Abstract

We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons.

Citations

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

Cited by

• Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
• Random k-out subgraph leaves only O(n/k) inter-component edges
• The MST of Symmetric Disk Graphs (in Arbitrary Metrics) is Light
• Planar Length-Constrained Minimum Spanning Trees
• Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex
• Tree Path Minimum Query Oracle via Boruvka Trees
• Algorithmes auto-stabilisants pour la construction d'arbres couvrants et la gestion d'entités autonomes
• Some Network Optimization Models under Diverse Uncertain Environments
• On-Demand Multimedia Delivery in 6G: An Optimal-Cost Steiner Tree Approach
• Parallel batch queries on dynamic trees: algorithms and experiments
• Can't See The Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners
• GrAviPaSt's Lens to the Past: Unveiling the Evolution of Filamentary Structures
• Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs
• Minimum-weight spanning tree algorithms A survey and empirical study
• Random Spanning Trees and the Prediction of Weighted Graphs
• An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem
• Near-optimal labeling schemes for nearest common ancestors
• A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)
• Otakar Borůvka on minimum spanning tree problem Translation of both the 1926 papers, comments, history
• Nearest Common Ancestors: A Survey and a New Algorithm for a Distributed Environment
• Theory of minimum spanning trees. II. Exact graphical methods and perturbation expansion at the percolation threshold
• New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
• A Stronger Lower Bound on Parametric Minimum Spanning Trees
• Work-Efficient Batch-Incremental Minimum Spanning Trees with Applications to the Sliding-Window Model
• On Cartesian Trees and Range Minimum Queries
• Graphic matroid [wikipedia]
• Minimum spanning tree [wikipedia]
• Otakar Borůvka [wikipedia]
• A novel approach for quantitative assessment of mucosal damage in inflammatory bowel disease. [europepmc]
• Resilient Wireless Sensor Networks Using Topology Control: A Review. [europepmc]
• A construction heuristic for the capacitated Steiner tree problem. [europepmc]
• Faster Cut Sparsification of Weighted Graphs. [europepmc]

Related

• Minimum-weight Spanning Tree Construction in O(log log log n) Rounds on the Congested Clique
• Stochastic Minimum Spanning Trees with a Single Sample
• Binary weights spanning trees and the k-red spanning tree problem in linear time
• Models of random spanning trees
• An almost-linear time algorithm for uniform random spanning tree generation