I need to determine Minimum Spanning Trees (MST) of very big complete graphs, whose edgeweights can be calculated from data that is associated with the vertices.
In the planar euclidean case, for example, the edgeweights correspond to euclidean distances between points to which the adjacent vertices map; in that case the vertex degree of the MST can't be more than 6 and consequently it would suffice to calculate the MST in the Subgraph $S\subseteq G$ that is induced by the 6 edges of smallest weight that are adjacent to each vertex, albeit that would be inferior to calculate the MST of the graph that is induced by the Delaunay Triangulation of the pointset.
Now my idea would be to assume a reasonable upper bound $k$ on the degree of vertices of the MSTs of graphs with edgeweights that can be calculated deterministically from information associated with the vertices and take and attempt to calculate the MST in the Subgraph that is induced by the sets of the $k$ shortest edges adjacent to the individual vertices; that would reduce the storage requirements from $O(n^2)$ to $O(n)$.
The case that the vertex degree of an MST is higher than the assumed $k$ can be detected during the calculation of of the MST and, if a vertex "runs out" of adjacent edges, the next $k$ of the shortest adjacent edges can be determined in $O(n)$ time and added to S to keep the algorithm going.
Question:
has the problem of determining MSTs in very big graphs, with edgeweights calculated deterministically from data that is associated with the vertices, already been investigated and what are (free) online ressources can be recommended?
