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 the tempest with a crash of wood
Throws down in front of us is not to bar
Our passage to our journey’s end for good,
But just to ask us who we think we are....”
—Robert Frost (1874–1963)