A randomized linear-time algorithm to find minimum spanning trees

1995/03/01 by David R. Karger, Philip N. Klein, Robert E. Tarjan · 14 citations
Computer Science · #Algorithms and Data Compression #Data Management and Algorithms #Data Mining Algorithms and Applications

paper · pdf · doi:10.1145/201019.201022

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
• 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