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:
“On a tree by a river a little tom-tit
Sang “Willow, titwillow, titwillow!”
And I said to him, “Dicky-bird, why do you sit
Singing, ‘Willow, titwillow, titwillow’?
Is it a weakness of intellect, birdie?” I cried,
“Or a rather tough worm in your little inside?””
—Sir William Schwenck Gilbert (1836–1911)