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: A hybrid evolutionary algorithm for the capacitated minimum spanning tree problemInfluential work since 2022
- Pick up a classic book: MetaheuristicsThe most-reprinted book on the subject
- Read the landmark paper: Multi-exchange neighborhood structures for the capacitated minimum spanning tree problemCited 122 times
- Go sideways: Borůvka's algorithmA closely related topic
- Go sideways: Expected linear time MST algorithmA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🏆 Landmark papers (most cited)
Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem
The Capacitated Minimum Spanning Tree
A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem
A Memory Adaptive Reasoning Technique for Solving the Capacitated Minimum Spanning Tree Problem
A biased random-key genetic algorithm for the capacitated minimum spanning tree problem
Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
A branch and bound algorithm for the capacitated minimum spanning tree problem
Savings based ant colony optimization for the capacitated minimum spanning tree problem
🆕 Influential since 2022
A hybrid evolutionary algorithm for the capacitated minimum spanning tree problem
Scatter search for capacitated minimum spanning tree
A novel three-stage matheuristic for the capacitated minimum spanning tree problem with time windows
Valid inequalities for the non-unit demand capacitated minimum spanning tree problem with arc time windows and flow costs
📚 Books worth reading
MetaheuristicsMauricio G. C. Resende, Jorge Pinho de Sousa · 2004- 📕Fuzzy systems and data mining IIITaiwan) FSDM (Conference) (2017 Hualien · 2017
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…