Editing Minimum spanning tree (section)

==Applications==
Minimum spanning trees have direct applications in the design of networks, including [[computer network]]s, [[telecommunications network]]s, [[transport network|transportation network]]s, [[water supply network]]s, and [[electrical grid]]s (which they were first invented for, as mentioned above).<ref>{{citation |last1=Graham |first1=R. L. |title=On the history of the minimum spanning tree problem |journal=Annals of the History of Computing |volume=7 |issue=1 |pages=43–57 |year=1985 |doi=10.1109/MAHC.1985.10011 |mr=783327 |s2cid=10555375 |last2=Hell |first2=Pavol |author1-link=Ronald Graham |author2-link=Pavol Hell}}</ref> They are invoked as subroutines in algorithms for other problems, including the [[Christofides algorithm]] for approximating the [[traveling salesman problem]],<ref>[[Nicos Christofides]], [https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf Worst-case analysis of a new heuristic for the travelling salesman problem], Report 388, Graduate School of Industrial Administration, CMU, 1976.</ref> approximating the multi-terminal minimum cut problem (which is equivalent in the single-terminal case to the [[maximum flow problem]]),<ref>{{cite journal |last1=Dahlhaus |first1=E. |last2=Johnson |first2=D. S. |author2-link=David S. Johnson |last3=Papadimitriou |first3=C. H. |author3-link=Christos Papadimitriou |last4=Seymour |first4=P. D. |author4-link=Paul Seymour (mathematician) |last5=Yannakakis |first5=M. |author5-link=Mihalis Yannakakis |date=August 1994 |title=The complexity of multiterminal cuts |url=http://akpublic.research.att.com/~dsj/papers/3way.pdf |url-status=dead |journal=[[SIAM Journal on Computing]] |volume=23 |issue=4 |pages=864–894 |doi=10.1137/S0097539792225297 |archive-url=https://web.archive.org/web/20040824184059/http://akpublic.research.att.com/~dsj/papers/3way.pdf |archive-date=24 August 2004 |access-date=17 December 2012}}</ref>
and approximating the minimum-cost weighted perfect [[matching (graph theory)|matching]].<ref>{{cite conference |last1=Supowit |first1=Kenneth J. |last2=Plaisted |first2=David A. |last3=Reingold |first3=Edward M. |year=1980 |title=Heuristics for weighted perfect matching |url=http://dl.acm.org/citation.cfm?id=804689 |conference=12th Annual ACM Symposium on Theory of Computing (STOC '80) |location=New York, NY, USA |publisher=ACM |pages=398–419 |doi=10.1145/800141.804689}}</ref>

Other practical applications based on minimal spanning trees include:
* [[Taxonomy (general)|Taxonomy]].<ref>{{cite journal |last=Sneath |first=P. H. A. |date=1 August 1957 |title=The Application of Computers to Taxonomy |journal=Journal of General Microbiology |volume=17 |issue=1 |pages=201–226 |doi=10.1099/00221287-17-1-201 |pmid=13475686 |doi-access=free}}</ref>
* [[Cluster analysis]]: clustering points in the plane,<ref>{{cite conference |last1=Asano |first1=T. |author1-link=Tetsuo Asano |last2=Bhattacharya |first2=B. |last3=Keil |first3=M. |last4=Yao |first4=F. |author4-link=Frances Yao |year=1988 |title=Clustering algorithms based on minimum and maximum spanning trees |conference=Fourth Annual Symposium on Computational Geometry (SCG '88) |volume=1 |pages=252–257 |doi=10.1145/73393.73419}}</ref> [[single-linkage clustering]] (a method of [[hierarchical clustering]]),<ref>{{cite journal |last1=Gower |first1=J. C. |last2=Ross |first2=G. J. S. |year=1969 |title=Minimum Spanning Trees and Single Linkage Cluster Analysis |journal=Journal of the Royal Statistical Society |series=C (Applied Statistics) |volume=18 |issue=1 |pages=54–64 |doi=10.2307/2346439 |jstor=2346439}}</ref> graph-theoretic clustering,<ref>{{cite journal |last=Päivinen |first=Niina |date=1 May 2005 |title=Clustering with a minimum spanning tree of scale-free-like structure |journal=Pattern Recognition Letters |volume=26 |issue=7 |pages=921–930 |bibcode=2005PaReL..26..921P |doi=10.1016/j.patrec.2004.09.039}}</ref> and clustering [[gene expression]] data.<ref>{{cite journal |last1=Xu |first1=Y. |last2=Olman |first2=V. |last3=Xu |first3=D. |date=1 April 2002 |title=Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees |journal=Bioinformatics |volume=18 |issue=4 |pages=536–545 |doi=10.1093/bioinformatics/18.4.536 |pmid=12016051 |doi-access=free}}</ref>
* Constructing trees for [[broadcasting (networking)|broadcasting]] in computer networks.<ref>{{cite journal |last1=Dalal |first1=Yogen K. |last2=Metcalfe |first2=Robert M. |date=1 December 1978 |title=Reverse path forwarding of broadcast packets |journal=Communications of the ACM |volume=21 |issue=12 |pages=1040–1048 |doi=10.1145/359657.359665 |s2cid=5638057 |doi-access=free}}</ref>
* [[Image registration]]<ref>{{cite conference |last1=Ma |first1=B. |last2=Hero |first2=A. |last3=Gorman |first3=J. |last4=Michel |first4=O. |year=2000 |title=Image registration with minimum spanning tree algorithm |url=http://web.eecs.umich.edu/~hero/Preprints/MinimumSpanningTree.pdf |conference=International Conference on Image Processing |volume=1 |pages=481–484 |doi=10.1109/ICIP.2000.901000 |archive-url=https://ghostarchive.org/archive/20221009/http://web.eecs.umich.edu/~hero/Preprints/MinimumSpanningTree.pdf |archive-date=2022-10-09 |url-status=live}}</ref> and [[Image segmentation|segmentation]]<ref>P. Felzenszwalb, D. Huttenlocher: Efficient Graph-Based Image Segmentation. IJCV 59(2) (September 2004)</ref> – see [[minimum spanning tree-based segmentation]].
* Curvilinear [[feature extraction]] in [[computer vision]].<ref>{{cite journal |last1=Suk |first1=Minsoo |last2=Song |first2=Ohyoung |date=1 June 1984 |title=Curvilinear feature extraction using minimum spanning trees |journal=Computer Vision, Graphics, and Image Processing |volume=26 |issue=3 |pages=400–411 |doi=10.1016/0734-189X(84)90221-4}}</ref>
* [[Handwriting recognition]] of mathematical expressions.<ref>{{cite book |last1=Tapia |first1=Ernesto |title=Graphics Recognition. Recent Advances and Perspectives |last2=Rojas |first2=Raúl |publisher=Springer-Verlag |year=2004 |isbn=978-3540224785 |series=Lecture Notes in Computer Science |volume=3088 |location=Berlin Heidelberg |pages=329–340 |chapter=Recognition of On-line Handwritten Mathematical Expressions Using a Minimum Spanning Tree Construction and Symbol Dominance |chapter-url=http://page.mi.fu-berlin.de/rojas/2003/grec03.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://page.mi.fu-berlin.de/rojas/2003/grec03.pdf |archive-date=2022-10-09 |url-status=live}}</ref>
* [[Circuit design]]: implementing efficient multiple constant multiplications, as used in [[finite impulse response]] filters.<ref>{{cite conference |last1=Ohlsson |first1=H. |year=2004 |title=Implementation of low complexity FIR filters using a minimum spanning tree |conference=12th IEEE Mediterranean Electrotechnical Conference (MELECON 2004) |volume=1 |pages=261–264 |doi=10.1109/MELCON.2004.1346826}}</ref>
* [[Regionalisation]] of socio-geographic areas, the grouping of areas into homogeneous, contiguous regions.<ref>{{cite journal |last=Assunção |first=R. M. |author2=M. C. Neves |author3=G. Câmara |author4=C. Da Costa Freitas |year=2006 |title=Efficient regionalization techniques for socio-economic geographical units using minimum spanning trees |url=https://zenodo.org/record/3832352 |journal=International Journal of Geographical Information Science |volume=20 |issue=7 |pages=797–811 |doi=10.1080/13658810600665111 |bibcode=2006IJGIS..20..797A |s2cid=2530748}}</ref>
* Comparing [[ecotoxicology]] data.<ref>{{cite journal |last1=Devillers |first1=J. |last2=Dore |first2=J.C. |date=1 April 1989 |title=Heuristic potency of the minimum spanning tree (MST) method in toxicology |journal=Ecotoxicology and Environmental Safety |volume=17 |issue=2 |pages=227–235 |doi=10.1016/0147-6513(89)90042-0 |pmid=2737116|bibcode=1989EcoES..17..227D }}</ref>
* Topological [[observability]] in power systems.<ref>{{cite journal |last1=Mori |first1=H. |last2=Tsuzuki |first2=S. |date=1 May 1991 |title=A fast method for topological observability analysis using a minimum spanning tree technique |journal=IEEE Transactions on Power Systems |volume=6 |issue=2 |pages=491–500 |bibcode=1991ITPSy...6..491M |doi=10.1109/59.76691}}</ref>
* Measuring homogeneity of two-dimensional materials.<ref>{{cite journal |last1=Filliben |first1=James J. |last2=Kafadar |first2=Karen |author2-link=Karen Kafadar |last3=Shier |first3=Douglas R. |date=1 January 1983 |title=Testing for homogeneity of two-dimensional surfaces |journal=Mathematical Modelling |volume=4 |issue=2 |pages=167–189 |doi=10.1016/0270-0255(83)90026-X |doi-access=}}</ref>
* Minimax [[process control]].<ref>{{citation |last1=Kalaba |first1=Robert E. |title=Graph Theory and Automatic Control |year=1963 |url=http://www.dtic.mil/dtic/tr/fulltext/u2/297072.pdf |archive-url=https://web.archive.org/web/20160221191747/http://www.dtic.mil/dtic/tr/fulltext/u2/297072.pdf |archive-date=February 21, 2016 |url-status=dead}}</ref>
* Minimum spanning trees can also be used to describe financial markets.<ref>Mantegna, R. N. (1999). [[arxiv:cond-mat/9802256|Hierarchical structure in financial markets]]. The European Physical Journal B-Condensed Matter and Complex Systems, 11(1), 193–197.</ref><ref>Djauhari, M., & Gan, S. (2015). [https://www.researchgate.net/profile/Maman_Djauhari3/publication/277250327_Optimality_problem_of_network_topology_in_stocks_market_analysis/links/59ebdb7d4585151983cb7795/Optimality-problem-of-network-topology-in-stocks-market-analysis.pdf Optimality problem of network topology in stocks market analysis]. Physica A: Statistical Mechanics and Its Applications, 419, 108–114.</ref> A correlation matrix can be created by calculating a coefficient of correlation between any two stocks. This matrix can be represented topologically as a complex network and a minimum spanning tree can be constructed to visualize relationships.