Preprints (rote Reihe) des Fachbereich Mathematik
Refine
Year of publication
- 1992 (1)
Document Type
- Report (1) (remove)
Language
- English (1)
Has Fulltext
- yes (1) (remove)
Faculty / Organisational entity
228
Weighted k-cardinality trees
(1992)
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.