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: Distributed minimum spanning tree approach for critical load restoration using microgrid formation in resilient distribution systemsInfluential work since 2022
- Pick up a classic book: Discrete mathematicsThe most-reprinted book on the subject
- Read the landmark paper: Distributed verification of minimum spanning treesCited 56 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)
Distributed verification of minimum spanning trees
A distributed algorithm for constructing a minimum diameter spanning tree
A faster distributed protocol for constructing a minimum spanning tree
Tight Bounds for Distributed Minimum-Weight Spanning Tree Verification
Distributed Minimum Spanning Tree Maintenance for Transient Node Failures
Distributed minimum spanning tree differential evolution for multimodal optimization problems
Uncertain Distribution-Minimum Spanning Tree Problem
A distributed algorithm for directed minimum-weight spanning tree
🆕 Influential since 2022
Distributed minimum spanning tree approach for critical load restoration using microgrid formation in resilient distribution systems
Modified minimum spanning tree based vertical fragmentation, allocation and replication approach in distributed multimedia databases
Target-based distributionally robust minimum spanning tree problem
Latency, capacity, and distributed minimum spanning trees
On the minimum spanning tree distribution in grids
📚 Books worth reading
Discrete mathematicsKenneth A. Ross · 1985
Algorithm designMichael T. Goodrich, Roberto Tamassia · 2001
Data structures, algorithms, and applications in C++Sartaj Sahni · 1998- 📕Corrections, improvements, simulations and optimistic algorithms for the distributed minimum spanning tree problemMichalis Faloutsos · 1994
- 📕Corrections, improvements, simulations and optiMSTic algorithms for the distributed minimum spanning tree problemMichalis Faloutsos · 1995
- 📕PODC 2006Colo.) ACM Symposium on Principles of Distributed Computing (25th 2006 Denver · 2006
Path problems in networksJohn S. Baras · 2010
Computer Networks & Communications (NetCom)Nabendu Chaki · 2013
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.…
- Spanning tree In the mathematical field of graph theory, a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of…