Optimizing constrained subtrees of trees

Optimizing constrained subtrees of trees

0.00 Avg rating0 Votes
Article ID: iaor19971113
Country: Netherlands
Volume: 71
Issue: 2
Start Page Number: 113
End Page Number: 126
Publication Date: Dec 1995
Journal: Mathematical Programming (Series A)
Authors: , ,
Keywords: combinatorial analysis, programming: dynamic
Abstract:

Given a tree G=(V,E) and a weight function defined on subsets of its nodes, the authors 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. The authors 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 they show that the convex hulls of the feasible solutions to both problems are related: the convex hull of solutions to the packing 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 they derive valid inequalities, and specify the convex hull when k•4.

Reviews

Required fields are marked *. Your email address will not be published.