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:
“There was not a tree as far as we could see, and that was many miles each way, the general level of the upland being about the same everywhere. Even from the Atlantic side we overlooked the Bay, and saw to Manomet Point in Plymouth, and better from that side because it was the highest.”
—Henry David Thoreau (1817–1862)