Live briefing
Everything about Minimum spanning tree
Least-weight tree connecting graph vertices
In graph theory, a minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Minimum spanning treeA 5-minute orientation
- Skim a recent paper: MS2OD: outlier detection using minimum spanning tree and medoid selectionInfluential work since 2022
- Pick up a classic book: Discrete Mathematics and Its ApplicationsThe most-reprinted book on the subject
- Read the landmark paper: An optimal minimum spanning tree algorithmCited 218 times
- Go sideways: Borůvka's algorithmA closely related topic
- Go sideways: Expected linear time MST algorithmA closely related topic
📖 Definitions
Noun A spanning tree that has minimum possible weight for a given graph.
🏆 Landmark papers (most cited)
An optimal minimum spanning tree algorithm
Minimum cost spanning tree games
Degree-constrained minimum spanning tree
On the generalized minimum spanning tree problem
On the minimum label spanning tree problem
On the minimum diameter spanning tree problem
The Capacitated Minimum Spanning Tree
Minimum-loss network reconfiguration: A minimum spanning tree problem
🆕 Influential since 2022
MS2OD: outlier detection using minimum spanning tree and medoid selection
Cosmology and neutrino mass with the minimum spanning tree
On Multi-Objective Minimum Spanning Tree Problem under Uncertain Paradigm
Brain Tumor Segmentation Based on Minimum Spanning Tree
Two‐phase strategies for the bi‐objective minimum spanning tree problem
📚 Books worth reading
Discrete Mathematics and Its ApplicationsKenneth H. Rosen · 1988
Introduction to AlgorithmsThomas H. Cormen, Charles E. Leiserson · 1990
Discrete mathematicsKenneth A. Ross · 1985
Data structures and algorithm analysis in CMark Allen Weiss · 1993
Data structures & algorithm analysis in JavaMark Allen Weiss · 1999- 📕MatheuristicsVittorio Maniezzo, Thomas Stützle · 2009
Fundamentals of data structures in CEllis Horowitz · 1993
The probabilistic minimum spanning tree problemDimitris Bertsimas · 1988
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Borůvka's algorithm Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph, or a minimum spanning forest in the case of a graph that is not…
- Expected linear time MST algorithm The expected linear time MST algorithm is a randomized algorithm for computing the minimum spanning forest of a weighted graph with no isolated vertices…
- Prim's algorithm In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset…
- Distributed minimum spanning tree The distributed minimum spanning tree (MST) problem involves the construction of a minimum spanning tree by a distributed algorithm, in a network where…
- K-minimum spanning tree The k-minimum spanning tree problem, studied in theoretical computer science, asks for a tree of minimum cost that has exactly k vertices and forms a subgraph…
- Parallel algorithms for minimum spanning trees In graph theory a minimum spanning tree (MST) T {\displaystyle T} of a graph G = ( V , E ) {\displaystyle G=(V,E)} with | V | = n {\displaystyle |V|=n}…
- Kruskal's algorithm Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree.…
- Euclidean minimum spanning tree A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system…