Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
k-minimum spanning tree
open-in-new
<p>The k-minimum spanning tree problem, studied in <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, asks for a tree of minimum cost that has exactly k <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a> and forms a subgraph of a larger graph. It is also called the k-MST or edge-weighted k-cardinality tree. Finding this tree is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>, but it can be approximated to within a constant <a href="/facts/Approximation_ratio/BWlf7M32">approximation ratio</a> in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>. </p>