Weighted k-cardinality trees: complexity and polyhedral structure

摘要: We consider the k-CARD TREE problem, i.e., problem of finding in a given undirected graph G subtree with k edges, having minimum weight. Applications this arise oil-field leasing and facility layout. Although general is shown to be strongly NP hard, it can solved polynomial time if itself tree. give an integer programming formulation efficient exact separation routine for set generalized subtour elimination constraints. The polyhedral structure convex hull solutions studied. © 1994 by John Wiley & Sons, Inc.