Editing Minimum spanning tree (section)

==Other variants==
{{regular_polygon_minimum_spanning_tree.svg}}

* The '''[[Steiner tree]]''' of a subset of the vertices is the minimum tree that spans the given subset. Finding the Steiner tree is [[NP-complete]].<ref>{{Garey-Johnson}}. ND12</ref>

* The '''[[k-minimum spanning tree|''k''-minimum spanning tree]] (''k''-MST)''' is the tree that spans some subset of ''k'' vertices in the graph with minimum weight.
* A set of '''k-smallest spanning trees''' is a subset of ''k'' spanning trees (out of all possible spanning trees) such that no spanning tree outside the subset has smaller weight.<ref>{{citation
 | last = Gabow | first = Harold N. | author-link = Harold N. Gabow
 | mr = 0441784
 | issue = 1
 | journal = [[SIAM Journal on Computing]]
 | pages = 139–150
 | title = Two algorithms for generating weighted spanning trees in order
 | volume = 6
 | year = 1977
 | doi=10.1137/0206011}}.</ref><ref>{{citation
 | last = Eppstein | first = David | author-link = David Eppstein
 | doi = 10.1007/BF01994879
 | mr = 1172188
 | issue = 2
 | journal = BIT
 | pages = 237–248
 | title = Finding the ''k'' smallest spanning trees
 | volume = 32
 | year = 1992| s2cid = 121160520 }}.</ref><ref>{{citation
 | last = Frederickson | first = Greg N.
 | doi = 10.1137/S0097539792226825
 | mr = 1438526
 | issue = 2
 | journal = [[SIAM Journal on Computing]]
 | pages = 484–538
 | title = Ambivalent data structures for dynamic 2-edge-connectivity and ''k'' smallest spanning trees
 | volume = 26
 | year = 1997| url = http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1888&context=cstech
 }}.</ref>  (Note that this problem is unrelated to the ''k''-minimum spanning tree.)
* The '''[[Euclidean minimum spanning tree]]''' is a spanning tree of a graph with edge weights corresponding to the Euclidean distance between vertices which are points in the plane (or space).
* The '''[[rectilinear minimum spanning tree]]''' is a spanning tree of a graph with edge weights corresponding to the [[rectilinear distance]] between vertices which are points in the plane (or space).
* The '''[[distributed minimum spanning tree]]''' is an extension of MST to the [[distributed computing|distributed model]], where each node is considered a computer and no node knows anything except its own connected links. The mathematical definition of the problem is the same but there are different approaches for a solution.
* The '''[[capacitated minimum spanning tree]]''' is a tree that has a marked node (origin, or root) and each of the subtrees attached to the node contains no more than ''c'' nodes. ''c'' is called a tree capacity. Solving CMST optimally is [[NP-hard]],<ref>{{citation
 | last1 = Jothi | first1 = Raja
 | last2 = Raghavachari | first2 = Balaji
 | title = Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design
 | journal = ACM Trans. Algorithms
 | volume = 1
 | issue = 2
 | pages = 265–282
 | year = 2005
 | doi=10.1145/1103963.1103967
| s2cid = 8302085
 }}</ref> but good heuristics such as Esau-Williams and Sharma produce solutions close to optimal in polynomial time.
* The [[degree-constrained spanning tree|'''degree-constrained minimum spanning tree''']] is a MST in which each vertex is connected to no more than ''d'' other vertices, for some given number ''d''. The case ''d''&nbsp;=&nbsp;2 is a special case of the [[traveling salesman problem]], so the degree constrained minimum spanning tree is [[NP-hard]] in general.
* An [[Arborescence (graph theory)|'''arborescence''']] is a variant of MST for [[directed graph]]s. It can be solved in <math>O(E + V \log V)</math> time using the [[Chu–Liu/Edmonds algorithm]].
* A '''maximum spanning tree''' is a spanning tree with weight greater than or equal to the weight of every other spanning tree. Such a tree can be found with algorithms such as Prim's or Kruskal's after multiplying the edge weights by -1 and solving the MST problem on the new graph. A path in the maximum spanning tree is the [[widest path problem|widest path]] in the graph between its two endpoints: among all possible paths, it maximizes the weight of the minimum-weight edge.<ref>{{citation
 | last = Hu | first = T. C. | author-link = T. C. Hu
 | issue = 6
 | journal = Operations Research
 | pages = 898–900
 | title = The maximum capacity route problem
 | volume = 9
 | year = 1961
 | jstor=167055
 | doi=10.1287/opre.9.6.898| doi-access = 
 }}.</ref> Maximum spanning trees find applications in [[parsing]] algorithms for [[Natural language processing|natural languages]]<ref>{{cite conference
 | last1 = McDonald | first1 = Ryan
 | last2 = Pereira | first2 = Fernando
 | last3 = Ribarov | first3 = Kiril
 | last4 = Hajič | first4 = Jan
 | title = Non-projective dependency parsing using spanning tree algorithms
 | book-title = Proc. HLT/EMNLP
 | year = 2005
 | url = http://www.seas.upenn.edu/~strctlrn/bib/PDF/nonprojectiveHLT-EMNLP2005.pdf}}</ref> and in training algorithms for [[conditional random field]]s.
* The '''dynamic MST''' problem concerns the update of a previously computed MST after an edge weight change in the original graph or the insertion/deletion of a vertex.<ref>{{citation
 | last1 = Spira | first1 = P. M.
 | last2 = Pan | first2 = A.
 | mr = 0378466
 | issue = 3
 | journal = SIAM Journal on Computing
 | pages = 375–380
 | title = On finding and updating spanning trees and shortest paths
 | volume = 4
 | year = 1975
 | doi=10.1137/0204032| url = http://www.ics.forth.gr/~lourakis/10.1137.0204032.pdf
 }}.</ref><ref>{{citation
 | last1 = Holm | first1 = Jacob
 | last2 = de Lichtenberg | first2 = Kristian
 | last3 = Thorup | first3 = Mikkel | author3-link = Mikkel Thorup
 | doi = 10.1145/502090.502095
 | mr = 2144928
 | issue = 4
 | journal = [[Journal of the Association for Computing Machinery]]
 | pages = 723–760
 | title = Poly-logarithmic deterministic fully dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
 | volume = 48
 | year = 2001| s2cid = 7273552
 }}.</ref><ref>{{citation
 | last1 = Chin | first1 = F.
 | last2 = Houck | first2 = D.
 | journal = [[Journal of Computer and System Sciences]]
 | volume = 16
 | issue = 3
 | pages = 333–344
 | title = Algorithms for updating minimal spanning trees
 | year = 1978
 | doi=10.1016/0022-0000(78)90022-3| doi-access = 
 }}.</ref>
* The '''minimum labeling spanning tree problem''' is to find a spanning tree with least types of labels if each edge in a graph is associated with a label from a finite label set instead of a weight.<ref>{{citation
 | last1 = Chang | first1 = R.S.
 | last2 = Leu | first2 = S.J.
 | journal = [[Information Processing Letters]]
 | volume = 63
 | issue = 5
 | pages = 277–282
 | title = The minimum labeling spanning trees
 | year = 1997
 | doi=10.1016/s0020-0190(97)00127-0}}.</ref>
* A '''bottleneck edge''' is the highest weighted edge in a spanning tree. A spanning tree is a '''[[minimum bottleneck spanning tree]]''' (or '''MBST''') if the graph does not contain a spanning tree with a smaller bottleneck edge weight. A MST is necessarily a MBST ({{not a typo|provable}} by the [[#Cut property|cut property]]), but a MBST is not necessarily a MST.<ref>{{cite web|url=http://flashing-thoughts.blogspot.ru/2010/06/everything-about-bottleneck-spanning.html|title=Everything about Bottleneck Spanning Tree|website=flashing-thoughts.blogspot.ru|date=5 June 2010 |access-date=4 April 2018}}</ref><ref>{{Cite web |url=http://pages.cpsc.ucalgary.ca/~dcatalin/413/t4.pdf |title=Archived copy |access-date=2014-07-02 |archive-date=2013-06-12 |archive-url=https://web.archive.org/web/20130612080859/http://pages.cpsc.ucalgary.ca/~dcatalin/413/t4.pdf |url-status=dead }}</ref>
* A '''[[minimum-cost spanning tree game]]''' is a cooperative game in which the players have to share among them the costs of constructing the optimal spanning tree.
* The '''[[optimal network design]]''' problem is the problem of computing a set, subject to a budget constraint, which contains a spanning tree, such that the sum of shortest paths between every pair of nodes is as small as possible.