In mathematics, given an undirected graph with non-negative edge costs and an integer, the -minimum spanning tree, or -MST, of is a tree of minimum cost that spans exactly vertices of . A -MST does not have to be a subgraph of the minimum spanning tree (MST) of . This problem is also known as Edge-Weighted -Cardinality Tree (KCT).
The k-MST problem is shown to be NP-Hard by reducing the Steiner tree problem to the -MST problem. There are many constant factor approximations for this problem. The current best approximation is a 2-approximation due to Garg. This approximation relies heavily on the primal-dual schema of Goemans and Williamson.
When the -MST problem is restricted to the Euclidean plane, there exists a PTAS due to Arora.
Refer to KCTLIB for more information.
Famous quotes containing the word tree:
“The tree which moves some to tears of joy is in the eyes of others only a green thing that stands in the way. Some see nature all ridicule and deformity ... and some scarce see nature at all. But to the eyes of the man of imagination, nature is imagination itself.”
—William Blake (1757–1827)