The Edge-Weighted K-Cardinality Tree Problem
The k-Cardinality Tree (KCT) problem1 is a combinatorial optimization problem which generalizes the well known minimum weight spanning tree problem. It consists in finding in a node- or edge-weighted graph G=(V,E) a subtree with exactly k edges, such that the sum of the weights is minimal. The problem was first described in [18] and it has gained considerable interest in recent years due to various applications, e.g. in oil-field leasing [17], facility layout [14,13], open pit mining [24], matrix decomposition [6,7], quorum-cast routing [8] and telecommunications [16].