Premium
Weighted k ‐cardinality trees: Complexity and polyhedral structure
Author(s) -
Fischetti Matteo,
Hamacher Horst W.,
Jørnsten Kurt,
Maffioli Francesco
Publication year - 1994
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230240103
Subject(s) - combinatorics , convex hull , cardinality (data modeling) , integer programming , mathematics , tree (set theory) , polytope , integer (computer science) , discrete mathematics , graph , regular polygon , set (abstract data type) , time complexity , polyhedron , computer science , mathematical optimization , geometry , data mining , programming language
We consider the k ‐CARD TREE problem, i.e., the problem of finding in a given undirected graph G a subtree with k edges, having minimum weight. Applications of this problem arise in oil‐field leasing and facility layout. Although the general problem is shown to be strongly NP hard, it can be solved in polynomial time if G is itself a tree. We give an integer programming formulation of k ‐CARD TREE and an efficient exact separation routine for a set of generalized subtour elimination constraints. The polyhedral structure of the convex hull of the integer solutions is studied. © 1994 by John Wiley & Sons, Inc.