(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 E. Black.
Entry modified 17 July 2006.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Joseph L. Ganley, "minimum spanning tree", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 17 July 2006. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/minimumSpanningTree.html
