Minimum spanning tree

Summary

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components. There are many use cases for minimum spanning trees. One example is a telecommunications company trying to lay cable in a new neighborhood. If it is constrained to bury the cable only along certain paths (e.g. roads), then there would be a graph containing the points (e.g. houses) connected by those paths. Some of the paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. Curre

Official source

https://en.wikipedia.org/wiki/Minimum_spanning_tree

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (36)

Related publications

Related people (2)

Related people

Related units

Related concepts (17)

Related concepts

Related courses (15)

Related courses

Related lectures (41)

Related lectures

Fibonacci Heaps

Ali Chekir, Mohamed Slim Slama

Binomial heaps are data structures implemented as a collection of binomial trees, (A binomial tree of order K can be constructed from two trees of order (K-1)). They can implement several methods: Min, Insert, Union, ExtractMin, DecreaseKey and Delete. Fibonacci heaps are similar to binomial heaps,howevere it figured that they had a better performance in what regards the amortized analysis, These methods have a cost of O(1) except for ExtractMin and Delete (O(lg n)) Fibonacci heaps are used to improve the cost of Dijikstra and Prim. We implemented first the algorithms of Binomial and Fibonacci. We then used ExtractMin of fibonacci so as to implement Prim and Dijikstra. We have made a bonus algorithm , Kruskal who is also a "Minimum Spanning Tree" algorithm.

2006

We derive an asymptotic theorem generalizing in a sense the one by Beardwood et al. and Steele for the Traveling Salesman Problem, the minimun weight perfect matching problem and the minimum spanning tree problem on a random set of points in R^d, where the edge weight are taken to be equal to some power of the Euclidean distance. The rate of convergence was estimated by numerical experiments. These tend to show that for Euclidean distances, the length of the minimum spanning tree is asymptotically equal to slightly more than twice the weight of the optimum minimum perfect matching, while there seems to be a larger gap between the former and the length of the optimum traveling salesman tour.

1990

Right-Protected Data Publishing with Provable Distance-Based Mining

Nikolaos Freris

Protection of one's intellectual property is a topic with important technological and legal facets. We provide mechanisms for establishing the ownership of a dataset consisting of multiple objects. The algorithms also preserve important properties of the dataset, which are important for mining operations, and so guarantee both right protection and utility preservation. We consider a right-protection scheme based on watermarking. Watermarking may distort the original distance graph. Our watermarking methodology preserves important distance relationships, such as: the Nearest Neighbors (NN) of each object and the Minimum Spanning Tree (MST) of the original dataset. This leads to preservation of any mining operation that depends on the ordering of distances between objects, such as NN-search and classification, as well as many visualization techniques. We prove fundamental lower and upper bounds on the distance between objects post-watermarking. In particular, we establish a restricted isometry property, i.e., tight bounds on the contraction/expansion of the original distances. We use this analysis to design fast algorithms for NN-preserving and MST-preserving watermarking that drastically prune the vast search space. We observe two orders of magnitude speedup over the exhaustive schemes, without any sacrifice in NN or MST preservation.

Ieee Computer Soc2014