Preprints (rote Reihe) des Fachbereich Mathematik
Filtern
Erscheinungsjahr
- 1992 (1)
Dokumenttyp
- Bericht (1)
Sprache
- Englisch (1)
Volltext vorhanden
- ja (1) (entfernen)
Fachbereich / Organisatorische Einheit
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.