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:
“Every tree sends its fibres forth in search of the Wild. The cities import it at any price. Men plow and sail for it. From the forest and wilderness come the tonics and barks which brace mankind.”
—Henry David Thoreau (1817–1862)