TY - RPRT
A1 - Fischetti, Matteo
A1 - Hamacher, Horst W.
A1 - Jörnsten, Kurt
A1 - Maffioli, Francesco
T1 - Weighted k-cardinality trees
N2 - 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. While 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.
T3 - Preprints (rote Reihe) des Fachbereich Mathematik - 228
Y1 - 1992
UR - https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4883
UR - https://nbn-resolving.org/urn:nbn:de:hbz:386-kluedo-48838
ER -