Optimal subtrees and extensions
We consider the problem of finding an optimal family of nested rooted subtrees of a tree. We give a linear algorithm for the associated 1.p. for this problem. A generalization of this problem is that of finding an optimal "lower closed set" of nodes in an acyclic graph for which polyhedral and polarity characterization are given. these problem are useful relaxations when solving more complicated sequencing problems.
Record created on 2006-02-13, modified on 2016-08-08