Optimizing constrained subtrees of trees

El Houssaine Aghezzaf, Thomas Magnanti and Laurence Wolsey ()
Additional contact information
El Houssaine Aghezzaf: CORE, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium
Thomas Magnanti: CORE, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium
Laurence Wolsey: CORE, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium

No 1992050, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: Given a tree G = (V, E) and a weight function defined on subsets of its nodes, we consider two associated problems. The first, called the "rooted subtree problem" , is to find a maximum weight subtree, with a specified root, from a given set of subtrees. The second problem, called "the subtree packing problem" , is to find a maximum weight packing of node disjoint subtrees chosen from a given set of subtrees, where the value of each subtree may depend on its root. We show that the complexity status of both problems is related, and that the subtree packing problem is polynomial if and only if each rooted subtree problem is polynomial. In addition we show that the convex hulls of the feasible solutions to both problem is given by "pasting together" the convex hulls of the rooted subtree problems. We examine in detail the case where the set of feasible subtrees rooted at node i consists of all subtrees with at most k nodes. For this case we derive valid inequalities, and specify the convex hull when k ≤4.

Date: 1992-08-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1992.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1992050

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().