Optimizing constrained subtrees of trees

DOI10.1007/BF01585993zbMath0846.90114WikidataQ89214185 ScholiaQ89214185MaRDI QIDQ1914069

Thomas L. Magnanti, Laurence A. Wolsey, El-Houssaine Aghezzaf

Publication date: 3 October 1996

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

treedynamic programmingweight functioncolumn generationvalid inequalitiespolyhedral combinatoricsknapsacks with precedencemaximum weight subtreerooted subtree problemsubtree packing problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Related Items (5)

Extended formulations for the cardinality constrained subtree of a tree problem ⋮ The linking set problem: a polynomial special case of the multiple-choice knapsack problem ⋮ An efficient algorithm for a capacitated subtree of a tree problem in local access telecommunication networks ⋮ Optimizing constrained subtrees of trees ⋮ Finding a Maximum-Weight Convex Set in a Chordal Graph

Cites Work

• Unnamed Item
• Unnamed Item
• Packing and covering a tree by subtrees
• Polyhedral results for the precedence-constrained knapsack problem
• The node capacitated graph partitioning problem: A computational study
• Modelling piecewise linear concave costs in a tree partitioning problem
• Optimizing constrained subtrees of trees
• Optimal Subtrees and Extensions
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Efficient Algorithm for the Partitioning of Trees
• A Decomposition Algorithm for Local Access Telecommunications Network Expansion Planning

This page was built for publication: Optimizing constrained subtrees of trees