(definition)
Definition: A minimum-weight tree in a weighted graph which contains all of the graph's vertices.
Also known as MST, shortest spanning tree, SST.
Generalization (I am a kind of ...)
spanning tree.
Aggregate parent (I am a part of or used in ...)
Christofides algorithm (1).
See also Kruskal's algorithm, Prim-Jarnik algorithm, Boruvka's algorithm, Steiner tree, arborescence, similar problems: all pairs shortest path, traveling salesman.
Note: A minimum spanning tree can be used to quickly find a near-optimal solution to the traveling salesman problem.
The term "shortest spanning tree" may be more common in the field of operations research.
A Steiner tree is allowed additional connection points to reduce the total length even more.
Author: JLG
Eppstein's lecture outlining and contrasting MST algorithms.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 2 September 2014.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Joseph L. Ganley, "minimum spanning tree", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2014. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/minimumSpanningTree.html