{"id":26274,"date":"2017-10-26T20:45:08","date_gmt":"2017-10-26T15:15:08","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26274"},"modified":"2017-10-26T20:45:08","modified_gmt":"2017-10-26T15:15:08","slug":"applications-minimum-spanning-tree-problem","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/applications-minimum-spanning-tree-problem\/","title":{"rendered":"Applications of Minimum Spanning Tree Problem"},"content":{"rendered":"

Minimum Spanning Tree (MST) problem: Given connected graph G with positive edge weights, find a min weight set of edges that connects all of the vertices.<\/span><\/p>\n

MST is fundamental problem with diverse applications.<\/p>\n

\"Applications<\/p>\n

Network design.<\/strong>
\n\u2013 telephone, electrical, hydraulic, TV cable, computer, road<\/em>
\nThe standard application is to a problem like phone network design. You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn\u2019t a tree you can always remove some edges and save money.<\/p>\n

Approximation algorithms for NP-hard problems.<\/strong>
\n\u2013 traveling salesperson problem<\/a>, Steiner tree<\/a><\/em>
\nA less obvious application is that the minimum spanning tree can be used to approximately solve the traveling salesman problem. A convenient formal way of defining this problem is to find the shortest path that visits each point at least once.<\/p>\n

Note that if you have a path visiting all points exactly once, it\u2019s a special kind of tree. For instance in the example above, twelve of sixteen spanning trees are actually paths. If you have a path visiting some vertices more than once, you can always drop some edges to get a tree. So in general the MST weight is less than the TSP weight, because it\u2019s a minimization over a strictly larger set.<\/p>\n

On the other hand, if you draw a path tracing around the minimum spanning tree, you trace each edge twice and visit all points, so the TSP weight is less than twice the MST weight. Therefore this tour is within a factor of two of optimal.<\/p>\n[ad type=”banner”]\n

Indirect applications.<\/strong>
\n\u2013 max bottleneck paths
\n\u2013 LDPC codes for error correction
\n\u2013 image registration with Renyi entropy
\n\u2013 learning salient features for real-time face verification
\n\u2013 reducing data storage in sequencing amino acids in a protein
\n\u2013 model locality of particle interactions in turbulent fluid flows
\n\u2013 autoconfig protocol for Ethernet bridging to avoid cycles in a network<\/p>\n

Cluster analysis<\/strong>
\nk clustering problem can be viewed as finding an MST and deleting the k-1 most
\nexpensive edges.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"

Applications of Minimum Spanning Tree Problem-Minimum Spanning Tree Minimum Spanning Tree (MST) problem: Given connected graph G.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,76379],"tags":[70772,78066,78069,70795,78038,78067,78068,70779],"class_list":["post-26274","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-minimum-spanning-tree","tag-kruskals-algorithm-minimum-spanning-tree","tag-minimal-spanning-tree-algorithm","tag-minimum-spanning-tree-c","tag-minimum-spanning-tree-example","tag-minimum-spanning-tree-example-with-solution","tag-minimum-spanning-tree-geeksforgeeks","tag-minimum-spanning-tree-ppt","tag-minimum-spanning-tree-prims-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26274","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26274"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26274\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26274"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26274"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26274"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}