Algorithms for small spanning trees

In this paper we consider the well known NP-hard problem k-MST. We aregiven a weighted complete graph and we want to find a minimum weightspanning tree which spans only k vertices (with fixed k) of the graph.We consider the special case in which the edge weights correspond toEuclidean distances. This case is relevant for the applications inreal-time situations like fault-tolerant networks or oil rigslocation.Here, we propose two application algorithms, which are less effective(from the theoretical approximation point of view) that those presentin literature, but are more efficient. The efficiency of the algorithmis extremely important for the applications.We tested the performance of the proposed algorithms by comparing thesolutions found and the computation times with other known algorithms.