Packing and covering a tree by subtrees (Q1101129): Difference between revisions

The authors consider various generalization for the problem of packing subtrees into a tree, and describe the structure of the vertices for the polyhedra associated with these problems. They also give efficient algorithms for optimization over the polyhedra, and prove that the related problem of covering a tree by subtrees is polynomial-time solvable when the family of subtrees is ``fork-free'', using a reduction to a packing problem.