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 great pines stand at a considerable distance from each other. Each tree grows alone, murmurs alone, thinks alone. They do not intrude upon each other. The Navajos are not much in the habit of giving or of asking help. Their language is not a communicative one, and they never attempt an interchange of personality in speech. Over their forests there is the same inexorable reserve. Each tree has its exalted power to bear.”
—Willa Cather (1873–1947)